Time Complexity : 시간 복잡도란 알고리즘이 문제를 해결하는데 걸리는 시간과 공간을 얼마나 차지하는지 나타내는 정도를 말한다.
Algorism : 알고리즘이란 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거치는 과정들을 의미한다.
Complexity Analysis : 복잡도 분석. 시간과 공간의 복잡도가 알고리즘이 얼마나 효율적인지를 나타낸다.
복잡도가 작을 수록 빠른 시간내에 적은 공간을 소비하여 계산하기 때문에 좋은 코드라고 할 수 있다. 개발자로서 코드를 작성할 때 해당 코드의 복잡도를 파악하고 최대한 좋은 코드를 작성하는 습관을 들여야한다.
예시1) 복잡도를 구하기 위해서 2부터 16까지 두 수의 차 중 가장 큰 수를 구하는 공식을 작성한다고 가정해보자.
방법 1. 두 수의 차의 경우의 수를 모두 구하고 그 중에 가장 큰 수를 찾는다. n*n = n²
2 3 4 5 ... 16
2 0 1 2 3 ... 14
3 1 0 1 2 ... 13
4 2 1 0 1 ... 12
5 3 2 1 0 ... 11
... ... ... ... ... ... ...
16 14 13 12 11 ... 0방법 2. 가장 큰 수와 가장 작은 수를 찾아 그 둘의 차를 구한다. 2n
1) 첫번째 수부터 n번째 수까지 계속 비교하여 가장 작은 수를 찾는다. n번
2) 첫번째 수부터 n번째 수까지 계속 비교하여 가장 큰 수를 찾는다. n번
3) 1과 2에서 찾은 수의 차를 구한다.
2 3 4 5 ... 16
Is Smallest? Y N N N ... N
Is Largest? N N N N ... Y방법 3. 끝과 첫번째 수의 차를 구한다. n
앞서 2부터 16까지의 숫자가 차례로 나열되어있다는 걸 알기에 끝과 첫번째 의 차를 구하기만 하면 된다. 1번
시간 복잡도는 주로 빅-오표기법(Big-O Notaion)을 사용한다.
Big-O Notaion
Better Worse
Name | constant | logarithmic | linear | log linear | quadratic | qubic | exponential
Notation | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(n³) | O(cⁿ)위의 예시에서 방법1은 O(n²) / 방법2는 O(n) / 방법3은 O(1)이다.
빅-오표기법은 계수와 낮은 차수의 항은 표기를 하지 않는다. 방법2가 2n이지만 O(n)으로 표기하고 만약 복잡도가 4n² + 2n라면 O(n²)이 된다.
let person = {
name : 'jim',
age : '32',
hair : 'blond'
eye : 'blue'
}
let number = [4, 6, 10, 24, 64]O(1) – 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다. 그래서 아무리 데이터가 많이 들어와도 걸리는 시간은 일정하다.
O(log n) – 로그 시간 : 입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가진다.
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱이다.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱이다.
상수 시간 : 값을 찾을 때, 객체의 키나 배열의 인덱스를 알고 있다면 언제나 한 단계만 걸린다.
person.name //'jim'
number[0] //4로그 시간 : 배열에서 값을 찾을 때, 어느 쪽에서 시작할지를 알고 있으면 검색하는 시간이 두배로 줄어든다.
function findIdx(arr, num) {
for(let i = 0; i < arr.length; i++) {
if(arr[i] = num) {
return i
}
}
}
findIdx(arr, 4) //0
findIdx(arr, 24) //3지수 시간 : 보통 문제를 풀기 위해 모든 조합과 방법을 시도할 때 사용된다. 모든 경우의 수를 구하기 때문에 상당히 많은 시간과 공간이 소모된다.(예시1의 방법1)
자료구조별 시간복잡도
* Array
(순서가 일정하다)
Lookup(position) : 바로 찾고자 하는 인덱스를 검색 O(1)
Assign : 바로 바꾸고 싶은 인덱스에 새 값을 덮어쓰기 O(1)
Insert : arr에 있는 인덱스의 위치들을 바꾸고 추가 O(n)
Remove : 삭제한 인덱스에 뒷부분의 값을 앞으로 옮긴다 O(n)
FindValue : 찾고자 하는 값과 인덱스의 있는 값을 비교해서 찾는다 O(n)
* Linked Lists
(순서가 일정하지않아 head를 반드시 알아야한다.)
Lookup : 헤드부터 시작하여 하나씩 찾아야한다. O(n)
Find : 헤드부터 시작하여 하나씩 찾아야한다. O(n)
Assign : 헤드부터 시작하여 하나씩 찾아 해당 값을 변경한다. O(n)
Insert : 기존 값 사이에 추가하는 값과의 연결점을 만들어준다. 꼬리에 붙는다면 O(1), 중간에 붙인다면 보통 어떤 값에 붙일지 알고 있기때문에 O(1)
Remove : 제거하고픈 값의 전 값을 찾고 뒤의 값과 이어준다. O(n), 헤드에서 제거할 경우 이어주어야하는 값이 없기 때문에 O(1).
* Doubly-Linked Lists
(양방향으로 연결되어있다.)
Lookup : 헤드부터 시작하여 하나씩 찾아야한다. O(n)
Find : 헤드부터 시작하여 하나씩 찾아야한다. O(n)
Assign : 헤드부터 시작하여 하나씩 찾아 해당 값을 변경한다. O(n)
Insert : 기존 값 사이에 추가하는 값과의 연결점을 만들어준다. 꼬리에 붙는다면 O(1), 중간에 붙인다면 보통 어떤 값에 붙일지 알고 있기때문에 O(1)
Remove : 해당 값의 앞뒤 값을 알고 있어 바로 연결을 옮겨주면 되기 때문에 O(1).
* Tree
(내 값과 children의 값이 있다.)
트리의 경우 해당 값을 찾아야하기 때문에 기본적으로 O(n) 이다.
* Binary Search Tree
(왼쪽 자식의 값이 부모보다 작고 오른쪽 자식의 값이 부모보다 크다.)
이진 탐색트리는 조건이 있어 일반 트리구조보다 사용이 편리하지만 O(log n) 밸런스가 무너질 경우 O(n)이 될 수 도 있다. 그렇기 때문에 트리를 작성할 때 밸런스에 맞게 구조를 비틀어주어야한다.
Find : O(log n)
* Hash Table
Find : 키를 알고 있다면 바로 찾을 수 있다. O(1)
Assign : 바로 해당 값을 찾아 변경한다. O(1)
Insert : 해시 함수를 통과한 인덱스에 그대로 대입한다. O(1)
Remove : 바로 해당 값을 삭제한다. O(1).
단, 해쉬테이블은 충돌이 있으므로 O(n)까지 갈 수 있다.
