Big-O 표기법

Big-O 표기법이란?

시간복잡도를 나타내는 방법 중 하나

---

Big-O 복잡도

https://www.hackerearth.com/practice/notes/big-o-cheatsheet-series-data-structures-and-algorithms-with-thier-complexities-1/

• 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()