자료구조 summary, 시간복잡도

 

 

# 간단하게

// 1 : 가장빠름

// log(n) : 중

// n :느림

faster O(1) < O(log n) < O(nlog n) < O(n²) < O(2ⁿ) slower

slower로 갈수록(즉, 오른쪽 방향으로 갈수록) 효율성이 떨어집니다.

 

1. O(1) (constant)

입력데이터의 크기에 상관없이 언제나 처리속도는 동행하게 이루어진다.

ex) sorted Array search

 

2. O(log n) (logarithmic)

입력데이터의 크기가 커지더라도 처리속도가 크게 달라지지 않으며, 실행시간이 지날수록 처리해야 하는 데이터의 양이 절반으로 줄어드며 실행 시간은 증가하지만 속도는 감소한다.

ex) Binary search

 

3. O(n) (linear)

입력데이터의 크기에 비례해서 처리시간이 증가해 메모리의 사용이 정비례 한다(step : size = 1 : 1).

ex) search linked list, for문을 이용한 array 검색

 

4. O(n^2) (quadratic)

입력데이터의 크기에 따라 걸리는 시간은 제곱에 비례한다.

ex) 이중 for문

 

5. O(C^n) (exponential)

문제를 해결하기 위한 단계의 수는 주어진 상수값 C의 n제곱이다.

ex) 피보나치 수열, recursion