시간 복잡도
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는지
효율적인 알고리즘이란 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘!
우리는 시간 복잡도를 Big-O 표기법을 사용해 나타낸다.
Big-O
시간복잡도를 표기하는 방법 중 하나로 최악의 경우를 고려한다.
•
Big-O(빅-오) : 최악의 경우
•
Big-Ω(빅-오메가) : 최선의 경우
•
Big-θ(빅-세타) : 평균의 경우
우리는 Big-O를 통해 최악의 경우를 고려하여 알고리즘을 구현한다.
최악의 경우를 고려하여 대비하면 어디서 문제가 발생했는지 알아내기 더 수월하기때문
O(1)
constant complexity
입력값이 증가하더라도 시간이 늘어나지 않음
→ 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있다.
unction 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
JavaScript
복사
배열의 해당 index에 바로 접근하여 값을 반환 가능
O(n)
linear complexity
입력값이 증가함에 따라 시간 또한 같은 비율로 증가
function O_n_algorithm(n) { // O(n)
for (let i = 0; i < n; i++) {
// do something for 1 second
}
}
function another_O_n_algorithm(n) { // O(2n)
for (let i = 0; i < 2n; i++) {
// do something for 1 second
}
}
JavaScript
복사
O(2n)도 Big-O 표기법으로는 O(n)으로 표기한다.
→ 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기
O(log n)
logarithmic complexity
ex) BST에서 원하는 갑을 탐색할 때 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
O()
quadratic complexity
입력값이 증가함에 따라 시간이 n의 제곱수 비율로 증가
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
}
}
}
}
JavaScript
복사
for문이 중첩된 경우
O()
exponential complexity
Big-O 표기법 중 가장 느린 시간 복잡도
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
JavaScript
복사
시간 복잡도 예상하기
시간제한과 주어진 데이터 크기 제한에 따른 시간 복잡도를 어림잡아 예측할 수 있어야함
입력 데이터가 클 때는 O(n) 혹은 O(log n)의 시간 복잡도를 만족할 수 있도록 예측해서 문제를 풀고, 데이터가 작을 때는 문제를 풀어내는 것에 집중해야함
1. O(1) : 스택에서 Push, Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
5. O(
): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)6. O(
) : 피보나치 수열
출처:
[인생의 로그캣]