Complexity Analysis - 시간복잡도, Big-O Notation

복잡도 분석

• 어떤 문제를 푸는데 시간과 공간이 얼마나 필요한지에 대한 분석
• 시간과 공간 복잡도가 그 알고리즘이 얼마나 효율적인지를 나타내기 때문에 중요하다.

여기서는 시간 복잡도에 관한 내용만 다룬다.

 

 

아래 그림을 참고하여 두 수의 차가 가장 큰 수를 찾아보자.

 

 

방법 1. : 모든 숫자를 비교한다.

 

 

방법 2. : 가장 큰 수와 가장 작은 수를 찾은 후 (모든 수를 돌면서 가장 큰지/작은지 확인해야함) 비교한다.

 

방법 3. : 숫자가 정렬되어 있다면 가장 처음, 가장 마지막 숫자만 찾아서  비교한다.

 

 

시간 복잡도를 나타내는 방법 : Big-O Notation

 

보는 법 : 계산한 연산에서 상수를 제거하고 가장 큰 지수만 적어준다.

 

 

O(1) : constant

 

execution time : 일정한 시간을 유지한다.

 - array lookup

 - hash table insertion

 

 

 

 

 

 

O(log n) : logarithmic

execution time : 처음엔 빠르게 증가하다가 이후엔 천천히 증가한다.

 - Binary Search Tree

 

 

 

 

 

 

 

 

O(n) : linear

 

- linked list에서 찾는 것, array에서 찾는 것

 

 

 

O(n^2) : quadratic

 

문제가 증가할수록 시간이 기하급수적으로 증가한다.

 - 이중 중첩된 for loop 안에 constant time operation이 있는 경우

 

 

 

 

 

 

 

 

O(1) vs. O(n) vs. O(n^2) 

 

 

O(c^n) : exponential (worst)

 

 

실행 시간이 기하급수적으로 증가한다.

 - recursion

 - 메모이제이션을 쓰지 않은 피보나치수열