[TIL] 자료구조 - 복잡성

※ 시간 복잡도

- 시간 복잡도는 서로 다른 알고리즘들의 효율성을 비교할 때 사용한다.

 

규칙 1. 입력값(n)은 항상 0보다 크다

- 일반적으로 입력값이 음수일 수는 없기때문에 복잡도는 항상 0보다 크다는 가정을 하고 계산을 해야한다

 

규칙 2. 함수는 입력값이 많을수록 많은 작업을 한다

- 더 많은 입력값이 주어지면 작업을 하는 데 필요한 계산이나 처리시간이 길어진다.

 

규칙 3. 시간 복잡도에서는 모든 상수를 삭제한다.

- 만약 어떤 알고리즘의 복잡도가 3n이라면 3은 고려하지않고 복잡도는 n이 된다. 즉, 2n, 3n, 10n은 모두 복잡도가 n인 알고리즘이다.

 

규칙 4. 낮은 차수의 항은 무시한다

- 시간 복잡도에서 n과 n^2를 비교할땐 항상 n^2가 더 오래 걸리는 알고리즘이라고 판단한다.

하지만 예외인 예시들도 있는데 알고리즘에서는 작은값은 고려하지 않는게 대부분이기에 n이 무한으로 커지는 경우를 가정하고 비교해야 한다.

 

규칙 5. 시간 복잡도 함수가 log 함수를 포함할 경우 밑은 무시한다.

- 모든 로그는 서로 배수 관계로 복잡도에 관해 이야기를 할 경우엔 로그의 밑에 대해선 고려하지 않아도 된다. 로그의 밑은 무시하고 로그(logn) 알고리즘이라고만 칭하면 된다.

 

복잡도가 log인 알고리즘은 보통 무언가를 반으로 나누거나 2를 곱한 경우에 자주 사용된다.

그래서 for 반복문을 사용해 무언가를 탐색해 반으로 나누거나 2를 곱할 때 복잡도는 밑이 2인 로그가 된다.

 

규칙 6. 등호를 사용해 표현한다.

- 2n은 O(n)과 같다. 여기서 O(n)은 2n이 어떤 함수의 집합에 속한다는 의미를 가진다는 것을 알아두어야 한다.