빅오 표기법 (big O Notation)
빅오 슬라이드
코드 시간 재기
시간 복잡도: O(n)
//add_up_to_slower.js
function addUpTo(n) {
let total = 0;
for (let i = 1; i <= n; i++) {
total += i;
}
return total;
}
var t1 = performance.now();
addUpTo(1000000000);
var t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`)
//Time Elapsed: 1.4591999999284744 seconds.
시간 복잡도: O(1)
//add_up_to_faster.js
function addUpTo(n) {
return n * (n + 1) / 2; // 연산 3개 밖에 안함 O(3) -> O(1)
}
var time1 = performance.now();
addUpTo(1000000000);
var time2 = performance.now();
console.log(`Time Elapsed: ${(time2 - time1) / 1000} seconds.`)
Time Elapsed: 0.0003999999761581421 seconds.
시간 복잡도 시각화
https://rithmschool.github.io/function-timer-demo/
Big O Introduction
⌘ + click on a point to remove it; shift + click to remove all data for that function.
rithmschool.github.io
Q. 시간 복잡도는 ?
function logAtMost10(n) {
for (var i = 1; i <= Math.min(n, 10); i++) {
console.log(i);
}
}O(1)
function logAtLeast10(n) {
for (var i = 1; i <= Math.max(n, 10); i++) {
console.log(i);
}
}O(n)
공간 복잡도 (Space Complexity)
데이터를 담아놓는 양을 나타낸다.
Q. 공간복잡도는?
function logUpTo(n) {
for (var i = 1; i <= n; i++) {
console.log(i);
}
}O(1)
function logAtMost10(n) {
for (var i = 1; i <= Math.min(n, 10); i++) {
console.log(i);
}
}O(1)
function onlyElementsAtEvenIndex(array) {
var newArray = Array(Math.ceil(array.length / 2));
for (var i = 0; i < array.length; i++) {
if (i % 2 === 0) {
newArray[i / 2] = array[i];
}
}
return newArray;
}O(n)
function subtotals(array) {
var subtotalArray = Array(array.length); // 1. O(n)
for (var i = 0; i < array.length; i++) {
var subtotal = 0;
for (var j = 0; j <= i; j++) {
subtotal += array[j]; // 2. O(n)
}
subtotalArray[i] = subtotal;
}
return subtotalArray; // 1+2 => O(2n) => O(n)
}O(n)
Logarithms - 로그
log는 무엇인가? 지수함수의 역함이다.
나눗셈과 곱셈이 짝인것처럼 로그함수와 지수함수는 짝이다.
이진 로그를 대략 계산하기 위해서는
그 숫자가 1 보다 작아지기 전에 2로 나눠지는 횟수 이다.
로그
1. 특정 탐색 알고리즘이 로그 시간 복잡도를 가진다.
2. 효율적인 정렬 알고리즘도 로그 복잡도를 가진다.
3. 재귀가 가끔 로그 공간 복잡도를 가진다. (나중에 알게됨)
정리
1. 알고리즘의 성능을 분석하기 위해서, 빅오 표기법을 사용한다.
2. 빅오를 통해서 시간, 공간 복잡도에 대한 이해를 높일 수 있다.
3. 빅오는 정확도가 아니라 전체적인 추세를 중요하게 생각한다. (linear? quadratic? constand?)
4. 빅오로 측정되는 알고리즘의 시간과 공간 복잡도는 오직 알고리즘에만 의존한다. 하드웨어에 영향을 받지 않는다.
- 어느 알고리즘을 내 컴퓨터와 슈퍼컴퓨터에 실행하는 속도는 실제로 차이가 있겠지만, 전반적인 주제는 다르지 않다.
- 빅오는 실행될 연산의 갯수를 따지기 때문이다.
- 내 컴퓨터에서는 10 밀리초가 걸리고 다른 컴퓨터에서는 1 밀리초가 걸려도 그 실행차이는 중요하지 않다. 둘다 빅오가 작다는 것에 초점을 둔다
5. 빅오 표기법은 세상 모든 곳에서 사용된다.