데이터구조 수업을 이번에 듣게 되었는데, 학교에서는 c언어 중심으로 공부할 것 같은데 수업에 들어가기 전에 자바스크립트 중심으로 자료구조를 배우는 게 어떨까 싶어서 후다닥 간략하게 써보겠습니다.
교재로는 '자바스크립트로 하는 자료 구조와 알고리즘'을 선정하였습니다.
일반적으로 알고리즘의 속도를 성능의 척도로 사용한다. 그래서 우리는 시간 복잡도를 사용한다. 시간 복잡도 값을 얻기 위해서는 빅오표기법을 배워야 한다.
O(1)는 신성하다.
알고리즘이 얼마나 효과적인지 분석하는 방법으로 빅오 표기법을 사용한다.
빅오 표기법은 알고리즘의 최악의 경우 복잡도를 측정한다.
빅오 표기법으로 시간적(실행 시간)으로, 공간적(메모리)으로 알고리즘을 분석할 수 있다.
number of operations - 시간
amount of data - 자료 입력량
O(1)은 입력 공간에 대해 변하지 않는다. 따라서 O(1)을 상수 시간이라고 부른다.
이에 대한 예로는 배열에 있는 항목을 인덱스를 사용해 접근하는 경우가 있다.
O(n)은 선형 시간이고 최악의 경우에 n번의 연산을 수향해야 하는 알고리즘에 적용된다. n번을 실행하는 반복문을 떠오리면 된다.
O(n^2)은 2차 시간이고, O(n^3)은 3차 시간이다.
반복문 안에 반복문이라고 생각하면 좋다.
빅오 표기법 규칙
알고리즘의 시간 복잡도를 f(n)이라고 표현해보자. n은 입력의 개수를 나타낸다.
알고리즘 분석의 목표는 f(n)을 계산함으로써 알고리즘의 효율성을 이해하는 것이다.
계산을 위해서는 게산 규칙이 필요하다.
-
계수 법칙 : 빅오에서 입력 크기가 클 때 계수를 무시할 수 있다.
∀k>0 s.t f(n)이 O(g(n))이면 kf(n)은 O(g(n))이다.
(k를 무시! 어차피 무한대에 가까운 수로 보내니깐.) -
합의 법칙 : 알고리즘 두 개의 시간 복잡도를 더하면 된다.
f(n)이 O(h(n))이고 g(n)이 O(p(n))이면
f(n) + g(n)은 O(h(n) + p(n))이다. -
곱의 법칙 : 중첩 for 루프를 생각하면 된다. (for문 안에 for문)
f(n)이 O(h(n))이고 g(n)이 O(p(n))이면
f(n)g(n)은 O(h(n)p(n))이다. -
다항 법칙 : 다항 시간 복잡도 (예를 들어 2차 시간 복잡도)
f(n)이 k차 다항식이면 f(n)은 O(n^k)이다.
요약
- 빅오 표기법은 알고리즘의 성능을 측정하기 사용된다.
- 시간과 데이터의 양을 토대로 성능 측정한다.
- 계수 법칙, 합의 법칙, 곱의 법칙, 다항 법칙으로 시간 복잡도를 계산하면 된다.
문제
다음 각 연습 코드의 시간 복잡도를 계산하라.
1번 문제
function someFunc () {
for (let i=0; i<n*1000; i++) {
for (let j=0; j<n*20; j++) {
console.log(i+j);
}
}
}O( 1000 f ( 20 g(n) ) )
= O (f(g(n)) = n^2
계수법칙으로 앞의 계수를 다 없애고 나면 2차 시간 복잡도가 나온다.
여기서 다항 법칙을 사용하면 n^2이 나온다.
2번 문제
function someFunc () {
for (let i=0; i<n; i++) {
for (let j=0; j<n; j++) {
for (let k=0; k<n; k++) {
for (let i=0; i<10; i++) {
console.log(i+j+k+l);
}
}
}
}
}10n^3 => n^3 (다항법칙, 계수법칙)
3번 문제
function someFunc () {
for (let i=0; i<1000; i++) {
console.log("hi");
}
}f(1000)이므로 상수 시간 복잡도를 갖는다.
O(1) = 상수 시간 복잡도
(그냥 n이 없으니 상수로 수렴한다고 생각하면 된다.)
4번 문제
function someFunc () {
for (let i=1; i<n; i=i*2) {
console.log(n);
}
}i가 n이 되는 순간까지 반복문이 실행되는데 i는 2가 계속 곱해진다.
따라서 O(log_2(n))이 된다.
추가 내용
- 최선의 경우 한 번에 찾을 때 -> Big-오메가
- 최악의 경우 배열의 길이만큼 걸릴 때 -> Big-O
- 평균의 경우 배열의 길이 중간만큼 걸릴 때 -> Big-세타
