-
Big-O 표기법Data Structure & Algorithm 2022. 3. 20. 23:32
Big-O 표기법이란?
시간복잡도를 나타내는 방법 중 하나
Big-O 복잡도
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
- n이 모두 같은 수일 때 위의 순서로 복잡도가 높아지며 수행 시간이 늘어남(성능이 떨어짐)
Big-O 표기법 4법칙
Big-O 표기법은 점근적 표기법을 따름
따라서 상수를 더하거나 곱하는 등의 표기를 따로 하지 않음
물론 실제 계산에서는 상수에 따라 성능이 달라질 수 있음- 계수 법칙
n이 무한에 가까울수록 상수(k)의 의미가 없어지기 때문에 계수를 생략 - 합의 법칙
Big-O 간 합산 가능 - 곱의 법칙
Big-O 간 곱셈 가능 - 다항 법칙
특정 함수가 3차 다항식이면 해당 함수의 Big-O 복잡도는 O(n³) 이 됨
정리
아래 두 항목이 가장 큰 특징
- 상수항 무시 O(7n + 4m) => O(n + m)
- 가장 큰 항 외엔 무시 O(n² + n) => O(n²)
Javascript 에서 성능 측정하는 두 가지 방법
- Date.getTime()
- console.time(), console.timeEnd()