시간복잡도

<시간복잡도>

 

#효율적인 방법을 고민한다 = 시간 복잡도를 고민한다

#시간복잡도를 고려한다 = 입력값의 변화에 따라 연산을 실행할때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가
효율적인 알고리즘을 구현한다 = 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다.

< Big-O 표기법 >
#시간 복잡도를 표기하는 방법
-Big-O(빅-오)
-Big-Ω(빅-오메가)
-Big-θ(빅-세타)
-위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.
-시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다.
-빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문입니다. "최소한 특정 시간 이상이 걸린다" 혹은 "이 정도 시간이 걸린다"를 고려하는 것보다 "이 정도 시간까지 걸릴 수 있다"를 고려해야 그에 맞는 대응이 가능합니다.
-최악의 경우도 고려하여 대비하는 것이 바람직합니다. 따라서 다른 표기법보다 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

입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있습니다. 예를 들어 arr의 길이가 100만이라도, 즉시 해당 index에 접근해 값을 반환할 수 있습니다.

< O(n) >

-linear complexity
-입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미.
-예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있습니다. 

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_n_algorithm 함수에선 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가합니다. 즉 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어나고 있습니다. 
another_O_n_algorithm 함수는 입력값이 1 증가할 때마다 코드의 실행 시간이 2초씩 증가합니다. 
위의 코드,밑의 코드 모두 O(n)으로 표기한다.


< O(log n) >

-logarithmic complexity
-Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가집니다.
-BST(Binary Search Tree)의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)입니다.


< O(n2) >

-quadratic complexity
-입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미
-2n, 5n을 모두 O(n)이라고 표현하는 것처럼, n3과 n5도 모두 O(n2)로 표기합니다. 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
}
}
}
}

< O(2의 n승) >

-exponential complexity
-Big-O 표기법 중 가장 느린 시간 복잡도

function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}

-재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘입니다.

---

<데이터 크기에 따른 시간 복잡도>
입력 데이터가 클 때는 O(n) 혹은 O(log n)의 시간 복잡도를 만족할 수 있도록 예측해서 문제를 풀어야 합니다. 그러나 주어진 데이터가 작을 때는 시간 복잡도가 크더라도 문제를 풀어내는 것에 집중하세요.

---

출처

코드스테이츠