시간복잡도

O(1): 배열에서 index에 해당하는 값을 찾을 때.
O(n):
for(let i = 0; i < n; i++) {
...
} 이나 n 대신 2n이나, 5n, 10n 일 때에서 이러한 시간복잡도가 적용됨.
O(log n)
logarithmic complexity라고 부르며 Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가집니다. BST(binary search tree)가 좋은 예이다.
O(n^2): quadratic complexity
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
// do something for 1 second
}
}
}
n^3과 n^5도 모두 O(n^2)로 표기합니다. n이 커질수록 지수가 주는 영향력이 퇴색되기 때문입니다.
O(2^n): exponential complexity, 가장 느린 시간 복잡도 임.
function fibonacci(n) {
if(n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
재귀로 구현하는 피보나치 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘입니다.
문제를 해결하기 위한 알고리즘의 로직을 구현할 때, 시간 복잡도를 고려한다는 것은 무슨 의미일까요?
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가.
Big-O: 상한 점근 (최악의 경우) , Big-omega: 하한 점근 (최선의 경우), Big-theta: 그 둘의 평균

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);
}

다음의 시간 복잡도를 가지는 알고리즘들이 있을 때, 가장 느린 것과 가장 빠른 것을 모두 고르면? (단, n >= 10,000)
가장 빠른 것: O(log n), 가장 느린 것: O(n!)

stack에서 찾을 수 있는 시간 복잡도는
1. 스택에 새로운 요소를 넣거나 뺄 때 발생하는 O(1)이 있습니다. (넣을 때와 뺄 때 가장 마지막 요소를 넣거나 뺍니다.)
2. 스택을 탐색하는 O(n)이 있습니다. (스택 한 번 순회)

다음과 같은 코드의 시간 복잡도는?
let i = n;
while(parseInt(i) > 0) {
i = i / 2;
}
답: O(log n): N이 주어졌을 때 계속해서 1/2씩 줄어들기 때문에 연산 횟수는 log2(n)이고 Big-O 표기법으로 나타내면 O(log n) 입니다.
다음과 같은 코드의 시간 복잡도를 올바르게 나타낸 것은?
for(let i = 0; i < n; i++) {
i *= k;
}
log base는 big O notation에서 중요하지 않기 때문에 사실상 log n이 정답.
수학적으론 k배수만큼 i가 커지며 n에 도달하고 있기 때문에 log(k) n.
log(base2)8 === 3, log(base3)27 === 3