시간 복잡도
실행 환경과 메모리 사용량에 따라 프로그램의 성능은 다르기 때문에 성능을 정확하게 측정하는 것은 불가능합니다. 그렇기 때문에 대략적인 성능 비교를 위한 상대적 표기법인 빅오 표기법을 사용하기로 했습니다.
// O(log n) 로그시간
for(leti=0; i<=n; i*=2){
// ...
}
// O(n) 선형시간
for(let i=0; i<n; i++){
// ...
}
// O(n log n) 선형 지수 시간
for(let i=0; i<n; i++){
for(let j=1; j<=n; j*=2){
// ...
}
}
// O(n^2) 2차시간
for(let i=0; i<n; i++){
for(let j=0; j<n; j++){
// ...
}
}
// 지수시간이나 팩토리얼 시간 등의 코드는 특정한 상황이 아니면 가급적 사용하면 안 되는 코드이므로
// 작성하지 않았습니다
빅오 표기법에서 식의 계수가 있거나 상수를 더하고 빼는 것은 보신 적이 없을 것입니다. 그 이유는 빅오표기법은 점근적 표기법을 따르기 때문입니다. 점근적 표기법은 함수의 증감 추세를 비교하는 방법이기 때문입니다.
빅오 표기법에는 네 가지 법칙이 있습니다.
계수 법칙
상수 k가 0보다 클 때 f(n) = O(g(n))이면 kf(n) = O(g(n))입니다. n이 무한에 가까울수록 k의 크기는 의미가 없기 때문입니다.
// 두 루프는 같은 O(n)으로 표기됩니다.
for(let i=0; i<n; i++){
// ...
}
for(let i=0; i<n*5; i++{
// ...
}
합의 법칙
f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) + g(n) = O(h(n)) + O(p(n))입니다. 빅오는 더해질 수 있습니다.
// 두 루프를 합쳐 O(n+m)으로 표기할 수 있습니다.
// 계수 법칙에 의해 5는 사라집니다.
for(let i=0; i<n; i++){
// ...
}
for(let i=0; i<m*5; i++{
// ...
}
곱의 법칙
f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) * g(n) = O(h(n)) * O(p(n))입니다. 빅오는 곱해질 수 있습니다.
// 두 루프를 곱해 O(n^2)으로 표기할 수 있습니다.
// 계수 법칙에 의해 5는 사라집니다.
for(let i=0; i<n; i++){
for(let i=0; i<n*5; i++){
// ...
}
}
다항 법칙
f(n)이 k차 다항식이면 f(n)은 O(n^k)입니다.
ya// 다음 루프는 O(n^3)으로 표기할 수 있습니다.
for(let i=0; i<n*n*n; i++){
// ...
}
여러가지 법칙이 있지만 총 두 가지만 기억하면 됩니다. 상수항은 무시되며, 이진 탐색 가장 큰 항 외엔 무시된다는 것입니다.
'DataScience > Data Structure' 카테고리의 다른 글
알고리즘 - 정렬 (0) | 2022.12.19 |
---|---|
알고리즘 - 이진탐색 (0) | 2022.12.19 |
자료구조 - 비선형 자료구조 (0) | 2022.12.15 |
자료 구조의 종류 - 단순 구조와 선형 구조 (1) | 2022.12.09 |
자료구조와 알고리즘을 공부해야 하는 이유? 자바스크립트 똑똑하게 쓰기! (0) | 2022.12.06 |