복잡도 분석, 시간복잡도

시간복잡도란 ?

• input에서 out이 될 때 가지 걸리는 시간
• 알고리즘을 구성한 명령어가 실행된 횟수(frequency of calling command)
• 알고리즘 배울 때의 핵심은 공간, 시간을 이용하는 것. 이 때, 공간과 시간은 거의 항상 반비례하다.
• 즉, 어떤 알고리즘이 얼마나 걸리느냐? 이다.(CPU 사용량)

공간복잡도

• 메모리를 얼마나 사용하는가(용량)
• 어던 알고리즘이 메모리를 얼마나 쓰느냐? (RAM 사용량)
• 공간이냐? 사긴이냐? 면 요즘은 시간이 우선이다.

시간복잡도를 고려하는 것은 최적화를 위해 필요하다.
다만, 데이터를 저장할 수 있는 메모리와 저장매채의 발전 덕에 과거보다는 덜 필요하긴하다.

시간복잡도 그래프(Big-O Complexity)

• 시간복잡도가 빠른순
  O(logn) > O(n) > O(nlogn)>O(n^2)>O(n^3)>O(2^n)>O(n!)

1. O(1) : 입력자료의 수에 관계없이 일정한 실행시간을 갖음
   알고리즘이 문제를 해결하는데 오직 한단계만 거침
   1. O(logn) : 데이터양이 N배 많아진다면 시간은 N배보다 조금 더 많아진다.(정비례x)
      입력자료의 수에 따라 시간이 흐를수록 시간이 조금씩 증가
      문제를 해결하는데 필요한 단계들이 연산마다 특정요인에 의해 줄어든다.
      
      EX > 큰 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타남
      EX > 이진탐색 같은 효율이 좋은 검색 알고리즘, 퀵 소트, 머지소트
2. O(n) : 입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우 -입력자료마다 일정 시간 할당
   문제를 해결하기 위한 단계의 수와 입력 값이 1:1관계
3. O(nlogn) : 큰 문제를 일정 크기 갖는 문제로 쪼개고(logn+logn+ .. + logn) 다시 그것을 모으는 경우
     EX > 효율 좋은 정렬 알고리즘
     EX > quick sorting / heap sorting 등
4. O(n^2) : 이중 루프내에서 입력 자료를 처리할 때
     EX > 인접행렬이용한 bfs/dfs 알고리즘
5. O(n^3) : 삼중 루프 내에서 입력자료 처리할 때

 

 

---

 

Array - Primitive data structure

메모리상에서 이어져있는 데이터 타입.(자바스크립트에선 이렇지 않지만, 전통적인 Array는 이렇다.)
Array는 원초적인 데이터 타입이다.(Primitive data strucutre)

• Insert : O(n) - linear time operation
• Remove : O(n) - insert와 remove 의 경우 전체 배열 위치의 옮겨야 하기때문에 
• Lookup(position) : O(1) - Index 로 찾음
• Assign : O(1) - 덮어쓰기때문에
• Find : O(n)

 

Linked Lists

Linked Lists 에서는 head값이 매우 중요하며, 포인터의 값이 어떤이유에서든지 끊어져 접근이 불가능하다면 더이상 사용할 수 없다고 보고 GC(Garbage Collector)가 이를 처리한다.

• lookup : O(n) - 랜덤값이라 어떠한 순서로 있는지 알 수 없음,최악의 경우 모든 data에 가야함
• Find : O(n)
• Assign :O(n)
• Insert : O(1) - 포인터만 변경하면 되므로!! (내가 어디에 추가하면되는지 알고있기때문에)
• remove : O(n + 1 ) - 찾는 값의 전의 값을 모르므로.

Doubly-linked list 는 Singly Linked List 와는 달리 전 값을 알수있으므로 시간복잡도가 조금 다른 양상을 보인다.

• Insert : O(1)
• Remove : O(1)
• Lookup : O(n)
• Find : O(n)
• Assign : O(n)

 

- Array : constant time lookup, linear insertion/removal
- Singly - Linked Lists : constant time insert, linear time lookup and removal
- Doubly - Linked Lists : constant time insert/removal, but each node takes up a little more space

 

Tree_Binary Search Tree

tree는 본인의 값과 children이라는 reference를 갖고있다.

• find : O(n) - 최악의 경우 모든 경우를 찾아봐야하므로.
  Binary Searching Tree의 경우 탐색속도가 올라가므로 O(log n)도 가능하다, 하지만 한쪽으로 치우친 이진탐색트리의 경우 링크드리스트와 매우 유사한 형태를 띄므로 O(n)이다.
  
  어떻게하면 방지할 수 있을까? -> Binary Search Tree - rebalance 추가할때마다 balance 조정

 

정렬된 배열(Array)과 Binary Search Tree를 비교했을때 BST를 사용할 이유가 있을까?
메모리 차지 유형에서(연속, 비연속) 차이가 있기때문에 메모리 효율의 관점에서 BST가 조금 더 낫다.

데이터의 장단점을 알아야 데이터 사용시에 효율적인 선택을 할수있기때문에 중요하다.

 

Hash Table

링크

• Insert : O(1) - 키(key)는 고유하며, 해시함수(hash function)의 결과로 나온 해시(hash)와 값(value)를 저장소에 넣으면 되기때문.(해시함수의 시간복잡도는 함게 고려하지 않는다.)
  최악의 경우 O(n)이 될 수 있다. -> 해시 충돌(collision)으로 인해 모든 bucket의 value들을 찾아봐야 하는 경우도 있기 때문이다.
• Deletion : O(1) - 키는 고유하며, 해시함수(hash function)의 결과로 나온 해시에 매칭되는 값을 삭제하면 되기때문,(해시함수 복잡도 고려x)- inssert 와 같은 맥락으로 최악의 경우 O(n)이된다.
• Search : O(1), O(n) Deletion과 유사

 

해시테이블 데이터 구조의 단점

• 순서가 있는 배열에는 어울리지 않는다.(순서가 중요한 데이터의 경우)
• 공간 효율성이 떨어진다. - 데이터가 저장되기 전에 미리 저장공간을 확보해 놓아야 한다.
  공간이 부족하거나 아예 채워지지 않은 경우가 생길 가능성이 있다.
•  Hash Function 의 의존도가 높다.
  평균 데이터 처리의 시간복잡도는 O(1)이지만, 이는 해시 함수의 연산을 고려하지 않은 결과이다.