2021/1/22 자료구조(4) Complexity Analysis🔎

Complexity Analysis

복잡도 분석이란? 알고리즘을 푸는 데 있어서 시간과 공간을 얼마나 차지하는지를 나타내는 지표. 이는 곧 해당 알고리즘이 얼마나 효율적인가를 나타낸다.

Big-O notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

Big-O마다 이름이 다 있음 그래프의 경사가 급격할 수록 알고리즘의 효율이 아주 별로인 것임

1) O(1): constant time
2) O(log n): logarithmic time
3) O(n): linear time
4) O(n log n): log linear time
5) O(n^2): quadratic time
6) O(n^3): cubic time
7) O(c^n): exponential time
8) O(n^c): polynomial time

Common Data Structure Operation

• 단일연결리스트와 더블연결리스트의 차이는 리무브에 있음. 더블연결리스트는 직전의 노드에 대한 정보를 갖고 있기 때문에 노드 삭제시 시간복잡도가 O(1)임. 그러나 단일연결리스트는 직전 노드에 대한 정보가 없어서, 앞에서 부터 조회해와야 함. 그래서 시간복잡도가 O(n)이 되어버림. 물론 시간복잡도는 더블연결리스트가 더 낮?지만, 데이터를 더 잡아먹음... 앞 뒤 노드 다 저장하니까...

• constant O(1) 예시
  : 배열에서 n번째 요소 찾기, 배열에서 n번째에 어싸인, 해쉬테이블 추가, 링크드리스트(insert / 어디에 추가할지 안다고 가정할 때), 링크드리스트 헤드리무브

• logarithmic O(log n) 예시
  : 바이너리서치트리에서 서치할 때 (밸런스가 안맞는 워스트 케이스(아래 이미지)의 경우 이거 리니어임)
  

• linear O(n) 예시
  : 링크드리스트(Lookup, find, assign), 배열 요소삽입 및 삭제, 배열 특정 값의 인덱스 찾기, 링크드리스트 중간에 있는 애 리무브, 트리 find

• quadratic O(n^2) 예시
  : 이중포문

• exponential O(c^n) 예시
  : 재귀로 피보나치 구현하기