시간 복잡도 표현 방법
O(1)
Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는 방법입니다. O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않습니다.
해시 테이블의 조합 및 삽입에 해당
function O_1_algorithm(arr, index) {
return arr[index];
}
let arr =[1, 2, 3, 4, 5];
let index =1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2
O(n)
O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미합니다.
function O_n_algorithm(n) {
for (let i = 0; i < n; i++) {
// do something for 1 second
}
}
function another_O_n_algorithm(n) {
for (let i = 0; i < 2n; i++) {
// do something for 1 second
}
}
O(log n)
BST(Binary Search Tree)에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듭니다. 이해하기 쉬운 게임으로 비유해 보자면 up & down을 예로 들 수 있습니다.
이진 검색이 해당
- 1~100 중 하나의 숫자를 플레이어1이 고른다 (30을 골랐다고 가정합니다).
- 50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
- 1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
- 25보다 크므로 up을 외친다.
- 경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.
O(n^2)
function O_quadratic_algorithm(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// do something for 1 second
}
}
}
function another_O_quadratic_algorithm(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) { // do something for 1 second } } } }
O(2^n)
O(2^n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다.
재귀함수가 이에 해당된다.
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘입니다.
데이터 크기에 따른 시간 복잡도
| 데이터 크기 제한 | 예상되는시간 복잡도 |
| n ≤ 1,000,000 | O(n) or O (logn) |
| n ≤ 10,000 | O(n2) |
| n ≤ 500 | O(n3) |
질문
- 가장 빠른/느린 시간 복잡도는 무엇일까요? O(1)/O(2^n)
- 효율적인 알고리즘을 구성했다 함은 무엇을 의미할까요? 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘
- 시간 복잡도는 A와 B의 비례함이 어느 정도인지를 나타냅니다. A와 B는 무엇일까요? A: 입력값 B: 연산 횟수
1. 두 알고리즘 A, B의 시간 복잡도가 각각 O(n), O(logn)이라면, 알고리즘 B가 알고리즘 A 보다 항상 빠르다.
항상 빠른 것은 아닙니다.
- n이 점점 커질수록 B가 더 빨라집니다.
- input이 1개일 경우 —> 둘 다 1
- input이 2개일 경우 —> 1 / 2
- input이 4개일 경우 —> 2 / 4
- input이 8개일 경우 —> 3 / 8
2. 다음 코드의 시간 복잡도를 Big-O 표기법으로 나타냈을 때 옳은 것을 고르세요.
function chooseOne(arr, index) {
return arr[index];
}
let arr = [1, 2, 3, 4, 5];
for(let i = 0; i < arr.length; i += 1){
let result = chooseOne(arr, i);
console.log(result);
}
O(n)
for 문 내의 코드가 arr의 길이만큼만 실행됩니다. arr의 길이를 n이라고 놓으면, O(n)이라고 쉽게 파악할 수 있습니다.
3. 다음의 시간 복잡도를 가지는 알고리즘들이 있을 때, 가장 느린 것과 가장 빠른 것을 모두 고르면? (단, n ≥ 10,000)
가장 빠른 것: O(log n)가장 느린 것: O(n!)
4. 다음과 같은 코드의 시간 복잡도로 올바른 것은?
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
// do something with i and j
}
}
O(n^2)
- n개의 i에 대해 각각 n개의 j를 가지고 로직을 수행하므로 O(n^2)의 시간 복잡도를 갖습니다. Big-O notation에서는 계수와 상수항을 제외하고 표현합니다.
- 버블 정렬같은 비효율적인 알고리즘이 이에 해당
5. 다음과 같은 코드의 시간 복잡도를 올바르게 나타낸 것은?
let i = n;
while (parseInt(i) > 0) {
i = i / 2;
}
O(log n)
N이 주어졌을 때 계속해서 1/2씩 줄어들기 때문에 연산 횟수는 log2(n)이고 Big-O 표기법으로 나타내면 O(log n) 입니다. 이진 검색이 해당
6. 다음과 같은 코드의 시간 복잡도를 올바르게 나타낸 것은?
for (let i = 0; i < n; i++) {
i *= k;
}