Time Complexity

시간복잡도란 문제를 해결하는데 걸리는 시간과 입력의 함수관계를 가리킵니다.

주로 빅-오 표기법을 사용하며 나타내며, 이 표기법은 계수와 낮은 차수의 항을 제외시키는 방법입니다.

쉽게 말해, 작성한 코드가 시간이 얼마나 걸리는지 나타내는 방법으로, 최악의 경우 얼마나 시간이 걸릴지 예상해보며,

다른 효율적인 방법을 찾기 위해 사용하게 됩니다.

 

대표적인 시간 복잡도들을 간단하게 정의해보면,

1) O(1) - constant : 입력값 n이 주어졌을 때, 알고리즘이 문제를 해결하는데 한 단계 만 거칩니다.

2) O(log n) - logarithmic : 입력값 n이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.

3) O(n) - linear : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.

4) O(n^2) - quadratic

5) O(c^n) - exponential

 

ex)

1) O(1) :

- 배열에서 값을 검색할 때, 인덱스값으로 바로 접근이 가능하므로 O(1)

- 배열에서 특정 인덱스 값을 수정하는 경우

- (single)연결리스트에서 값을 추가하는 경우

- (double)연결리스트에서 값을 삭제하는 경우

2) O(log n) :

- n개를 절반으로 계속해서 나누는 경우(Binary Search Tree에서 값을 찾는 경우)

3) O(n) :

- 배열에 어떤 값을 삽입/삭제하는 경우

- 어떤값을 value로 찾는 경우

- (single)연결리스트에서 값을 찾는 경우

- (single)연결리스트에서 중간값을 삭제하는 경우

4) O(c^n) :

- 중첩된 for문같은 경우