###Time Complexity란
시간 복잡도입니다..그게 뭘까요 바로 알고르즘을 코드로 구현하여 작동시킬 때 공간을 얼마나 차지하는 지 나타내는 것들 중에 시간을 나타내는 것입니다. 여기서 알고리즘이 무엇이냐 하면요..결과물을 만들어 내기 위해 거쳐야하는 과정들을 의미합니다. 수학문제를 풀려고 식을 적는게 알고리즘? 이다 라고 생각하고 있습니다.
다시 Time Complexity으로 넘어가서 기본적인 개념은 입력값의 변화에 따라 문제를 해결하는데 걸리는 시간의 비율이 어떻게 변화하는가를 나타낸 것입니다. 시간복잡도를 표현하는 다음과 같은 종류들이 있습니다
function 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
2. O(n)
: **입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것**
```js
function O_n_algorithm(n) {
for (let i = 0; i < n; i++) {
console.log(i);
}
}
function another_O_n_algorithm(n) {
for (let i = 0; i < 2n; i++) {
console.log(i);
}
}
let i = n
while(parseInt(i) > 0) {
i = i / 2
}
4. O(n^2)
: **입력값이 증가함에 따라 걸리는 시간이 제곱의 비율로 증가하는 것을 의미함**
```js
function O_quadratic_algorithm(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(j);
}
}
}
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
여기서 중요한점 하나는 O(1) > O(logn) > O(n) > O(n^2) > O(2^n) 순서로 빠르다