[Data Structure] Time Complexity (시간 복잡도)
시간 복잡도
시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용합니다. 시간 복잡도에는 몇 가지 규칙이 있습니다.
- input ≥ 0
- functions do more work: for more input
- drop all constants
- ignore lower order terms
- ignore the base of logs
- $2n = O(n)$ => $2 ∈ O(n)$
규칙 1. 입력값(n)은 항상 0보다 크다.
입력값이 음수일 수는 없습니다. 그래서 복잡도는 항상 0보다 크다고 가정하고 계산을 해야합니다.
규칙 2. 함수는 많은 입력값이 있을 때 더 많은 작업을 하게 됩니다.
더 많은 입력값이 주어지면 어떤 작업을 하는 데 필요한 계산이나 처리 시간이 길어집니다.
규칙 3. 시간 복잡도에서는 모든 상수를 삭제합니다.
만약 어떤 알고리즘의 복잡도가 $3n$ 이라면 3은 고려하지 않고 복잡도는 $n$이 됩니다. $2n$, $3n$, $10n$ 모두 복잡도가 $n$ 인 알고리즘입니다.
규칙 4. 낮은 차수의 항들은 무시합니다.**
시간 복잡도에서는 $n$ 과 $n^2$을 비교할 때에는 항상 $n^2$이 더 오래 걸리는 알고리즘이라고 판단합니다. 여기서 의문이 들 수 있는 점은 그래프에서 $(1,1)$인 지점 전까지는 $n$ 이 더 오래 걸릴 수 있다는 것입니다. 하지만 알고리즘에서는 입력값( $n$ )이 1보다 작은 값은 고려하지 않고 큰 값에 대해서만 생각을 하므로 $n$ 이 무한으로 커진 경우를 가정하고 비교해야 합니다.
이런 이유로 시간 복잡도에서는 낮은 차수의 항들은 무시합니다. $n^3 + n^2 + n$ 이라는 함수가 있을 때, $n$과 $n^2$은 알고리즘의 시간 복잡도에 영향을 미치지 않고, 입력값이 무한이 될 때 고려해야 할 부분은 $n^3$ 입니다. 다음 강의에서 이런 내용을 어떤 형식으로 표현해야 할지 배울 것입니다.
규칙 5. 시간 복잡도 함수가 log 함수를 포함할 경우 밑은 무시합니다.
모든 로그는 서로 배수 관계입니다. 그래서 복잡도에 관해서 이야기할 때는 로그의 밑에 대해서는 고려하지 않아도 됩니다. 로그의 밑은 무시하고 로그 ($logn$) 알고리즘이라고만 말하면 됩니다.
복잡도가 $log$인 알고리즘은 보통 무언가를 반으로 나누거나 2를 곱한 경우에 자주 사용됩니다. 그래서 만약 for 반복문을 사용해서 무언가를 탐색하면서 반으로 나누거나 2를 곱할 때 복잡도는 밑이 2인 로그가 됩니다. 10으로 나누거나 10을 곱하게 되면 밑이 10인 로그가 됩니다. 하지만 시간 복잡도를 표시할 때에는 로그의 밑은 무시하고 그냥 log n 복잡도를 가진다고 표현합니다.
규칙 6. 등호를 사용하여 표현합니다.
다음 강의에서 더 자세히 다루겠지만 $2n$ 은 $O(n)$ 과 같습니다. 여기서 $O(n)$ 은 $2n$ 이 어떤 함수의 집합에 속한다는 의미를 가집니다. 그렇기 때문에 아래와 같은 등호를 활용하여 이 관계를 수학적으로 쓸 수 있습니다.
$2n = O(n), 2n ∈ O(n)$
이번 자료 구조 수업을 통해서 여러 종류의 알고리즘을 배우게 될 겁니다. 예를 들어, 상수 시간에 작동하는 알고리즘을 하나 생각해봅시다. 이 알고리즘의 시간 복잡도는 1 또는 문자 C를 사용하여 나타냅니다. 한 번의 계산만 하면 되는 경우로 $n$ 과는 독립적인 관계를 가집니다. 또, 정렬이나 트리에서는 $logn$ 또는 $n^2$ 복잡도인 알고리즘들을 많이 보게 될 것입니다.
Leave a comment