시간 복잡도
시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용합니다. 시간 복잡도에는 몇 가지 규칙이 있습니다.
input ≥ 0
functions do more work for more input
drop all constants
ignore lower order terms
ignore the base of logs
2n = O(n) => 2n∈O(n)
규칙 1. 입력값(n)은 항상 0보다 크다.
규칙 2. 함수는 많은 입력값이 있을 때 더 많은 작업을 하게 됩니다.
규칙 3. 시간 복잡도에서는 모든 상수를 삭제합니다.
규칙 4. 낮은 차수의 항들은 무시합니다.
규칙 5. 시간 복잡도 함수가 log 함수를 포함할 경우 밑은 무시합니다.
모든 로그는 서로 배수 관계입니다. 그래서 복잡도에 관해서 이야기할 때는 로그의 밑에 대해서는 고려하지 않아도 됩니다. 로그의 밑은 무시하고 로그 (logn)알고리즘이라고만 말하면 됩니다.
복잡도가 logn 인 알고리즘은 보통 무언가를 반으로 나누거나 2를 곱한 경우에 자주 사용됩니다. 그래서 만약 for 반복문을 사용해서 무언가를 탐색하면서 반으로 나누거나 2를 곱할 때 복잡도는 밑이 2인 로그가 됩니다. 10으로 나누거나 10을 곱하게 되면 밑이 10인 로그가 됩니다. 하지만 시간 복잡도를 표시할 때에는 로그의 밑은 무시하고 그냥 log n 복잡도를 가진다고 표현합니다.
규칙 6. 등호를 사용하여 표현합니다.