알고리즘의 효율을 측정하려면 Big-O 표기법을 사용한다.
Big-O 표기법이 중요한 이유는 어떤 알고리즘이 작은 입력에서는 빠를 수 있지만 입력값이 많아진다면 느려질 경우가 발생하게 된다.
시간 복잡도(Time Complexity)
시간 복잡도란? 입력 크기에 따라 알고리즘이 얼마나 많은 연산을 수행하는지 나타내는 것이다.
위 그래프는 오른쪽 아래로 갈 수록 효율적인 알고리즘, 왼쪽 위로 갈 경우 비효율적인 알고리즘을 나타낸다.
Big - O 표기법은 가장 빠르게 증가하는 항만을 남기고 나머지는 무시해서 표현한다.
이렇게 표기하는 이유는 함수가 정확히 몇 개의 연산량이 중요한 것이 아닌 데이터가 늘어남에 따라서 어떤 식으로 연산량이 증가하는지가 중요하기 때문이다.
예시: T(N) = 2N^2 + 3N + 5 = O(N^2)
Big-O 표기법
1. O(1) - 상수 시간
int[] arr = { 10, 20, 30 };
Console.WriteLine(arr[0]);
// 시간복잡도 = O(1)2. O(log N) - 로그 시간
int n = 32;
while(n > 1) {
n /= 2;
Console.ReadLine(n);
}
// 시간복잡도 = O(log₂ 32) = O(log₂ N)3. 선형 시간 - O(N)
int[] arr = { 10, 20, 30, 40, 50 };
foreach (int num in arr) {
Console.WriteLine(num);
}
// 시간복잡도 = O(5 * N) = O(N)4. 선형 로그 시간 - O(n log N)
int n = 8;
for (int i = 1; i <= n; i++) {
int x = i;
while (x > 1) {
x /= 2;
Console.WriteLine($"i: {i}, x: {x}");
} }
// 시간복잡도 = 바깥 루프(n) + 안쪽 루프(log i) = O(n log n)5. 이중 반복 - O(N^2)
for (int i = 0; i < 3; i++){
for (int j = 0; j < 3; j++){
Console.Write("*");
} }
// 시간복잡도 = O(N^2)