Data Structure TIL 06
2021년 8월 24일에 작성된 문서 1번 입니다.
자료 구조 배운 내용을 정리했습니다.
Time Complexity
효율적인 방법을 고민한다는 것 =
시간 복잡도
를 고민한다는 것
시간 복잡도
시간 복잡도 : 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?
- 효율적인 알고리즘을 구현한다는 것 =
입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘
- 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다.
Big-O 표기법
Big-O 표기법은
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?
를 표기하는 방법입니다.
시간 복잡도를 표기하는 방법
- Big-O (빅-오)
- Big-Ω (빅-오메가)
- Big-θ (빅-세타)
- 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법.
- 이 중 Big-O 표기법이 가장 자주 사용.
빅오 표기법은 최악의 경우를 고려
"이 정도 시간까지 걸릴 수 있다"
를 고려
Big-O 표기.1 : O(1)
constant complexity
- constant complexity
- 입력값이 증가하더라도 시간이 늘어나지 않는다.
* 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다.
//O(1)의 시간 복잡도를 가진 알고리즘
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
- linear complexity
- 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미.
입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있습니다.
// O(n)의 시간 복잡도를 가진 알고리즘
function O_n_algorithm(n) {
for (let i = 0; i < n; i++) {
// do something for 1 second
}
}
// 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가
// 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어나고 있다.
function another_O_n_algorithm(n) {
for (let i = 0; i < 2n; i++) {
// do something for 1 second
}
}
// 같은 비율로 증가하고 있다면
// 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기
O(log n)
logarithmic complexity
- logarithmic complexity
- Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도
자료구조에서 배웠던 BST(Binary Search Tree)를 기억하시나요? BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듭니다. 이해하기 쉬운 게임으로 비유해 보자면 up & down을 예로 들 수 있습니다.
- 1~100 중 하나의 숫자를 플레이어1이 고른다 (30을 골랐다고 가정합니다).
- 50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
- 1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
- 25보다 크므로 up을 외친다.
- 경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.
- 매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어들기 때문에 최악의 경우에도 7번이면 원하는 숫자를 찾아낼 수 있게 된다.
- BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘
O(n2)
quadratic complexity
- quadratic complexity
- 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미.
예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n2)라고 표현합니다.
//O(n2)의 시간 복잡도를 가진 알고리즘
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
}
}
}
}
- 2n, 5n 을 모두 O(n)이라고 표현하는 것처럼, n3과 n5 도 모두 O(n2)로 표기.
O(n^2)
exponential complexity
- exponential complexity
- Big-O 표기법 중 가장 느린 시간 복잡도
종이를 42번 접으면 그 두께가 지구에서 달까지의 거리보다 커진다는 이야기를 들어보신 적 있으신가요? 고작 42번 만에 얇은 종이가 그만한 두께를 가질 수 있는 것은, 매번
접힐 때마다 두께가 2배
로 늘어나기 때문입니다. 구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋습니다.
//O(2n)의 시간 복잡도를 가지는 알고리즘
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
- 재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘
- 브라우저 개발자 창에서 n을 40으로 두어도 수초가 걸리는 것을 확인 가능.
- n이 100 이상이면 평생 결과를 반환받지 못할 수도 있다.
대략적인 데이터 크기에 따른 시간 복잡도
데이터 크기 제한 | 예상되는시간 복잡도 |
---|---|
n ≤ 1,000,000 | O(n) or O (logn) |
n ≤ 10,000 | O(n2) |
n ≤ 500 | O(n3) |
Written with StackEdit.
Author And Source
이 문제에 관하여(Data Structure TIL 06), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@heewonkim-dev/Data-Structure-TIL-01-08p3fgjk저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)