[JavaScript] bigO

1. 계수 법칙

f(n)f(n)f(n)이 O(g(n))O(g(n))O(g(n))라면, k⋅f(n)k \cdot f(n)k⋅f(n)도 O(g(n))O(g(n))O(g(n))이다.

• 쉽게 말하면: 상수를 곱해도 시간복잡도는 변하지 않는다!
• 비유:
  만약 어떤 사람이 n2n^2n2만큼의 일을 한다고 하면, 그 사람이 2배 빠르거나 3배 느리더라도 결국 하는 일의 성장 속도는 여전히 n2n^2n2이다.

---

2. 합의 법칙

f(n)f(n)f(n)이 O(h(n))O(h(n))O(h(n))이고 g(n)g(n)g(n)이 O(p(n))O(p(n))O(p(n))라면, f(n)+g(n)f(n) + g(n)f(n)+g(n)은 O(max⁡(h(n),p(n)))O(\max(h(n), p(n)))O(max(h(n),p(n)))이다.

• 쉽게 말하면: 두 개를 더하면, 큰놈이 시간복잡도를 결정한다!
• 비유:
  큰 나무와 작은 나무가 있다면, 멀리서 보면 큰 나무만 보인다. 작은 나무는 묻혀버리는 것처럼, 더 큰 시간복잡도가 지배한다.
  예: n2+nn^2 + nn2+n → 큰놈 n2n^2n2만 남아서 O(n2)O(n^2)O(n2).

---

3. 다항 법칙

f(n)f(n)f(n)이 kkk-차 다항식이면, O(nk)O(n^k)O(nk)이다.

• 쉽게 말하면: 다항식은 가장 큰 차수만 중요하다!
• 비유:
  학교 시험에서 점수가 100×n2+5n+10100 \times n^2 + 5n + 10100×n2+5n+10이라면, nnn이 엄청나게 커지면 100×n2100 \times n^2100×n2만 중요해진다. 나머지 5n5n5n이나 101010은 아무 의미가 없다.
  예: 3n3+5n+73n^3 + 5n + 73n3+5n+7 → O(n3)O(n^3)O(n3).

---

4. 곱의 법칙

f(n)f(n)f(n)이 O(h(n))O(h(n))O(h(n))이고 g(n)g(n)g(n)이 O(p(n))O(p(n))O(p(n))라면, f(n)⋅g(n)f(n) \cdot g(n)f(n)⋅g(n)은 O(h(n)⋅p(n))O(h(n) \cdot p(n))O(h(n)⋅p(n))이다.

• 쉽게 말하면: 두 개를 곱하면, 시간복잡도도 곱해진다!
• 비유:
  만약 한 사람이 nnn번 일을 하고, 또 다른 사람이 n2n^2n2번 일을 하면, 둘이 협력했을 때의 총 일의 크기는 n⋅n2=n3n \cdot n^2 = n^3n⋅n2=n3만큼 커진다.
  예: n2×log⁡nn^2 \times \log nn2×logn → O(n2log⁡n)O(n^2 \log n)O(n2logn).

---

5. 전의 법칙

f(n)∈O(g(n))f(n) \in O(g(n))f(n)∈O(g(n))이고 g(n)∈O(h(n))g(n) \in O(h(n))g(n)∈O(h(n))이면, f(n)∈O(h(n))f(n) \in O(h(n))f(n)∈O(h(n))이다.

• 쉽게 말하면: 중간 단계를 건너뛰고 최종적으로 더 큰 놈만 보면 된다!
• 비유:
  만약 f(n)f(n)f(n)이 g(n)g(n)g(n)보다 느리고, g(n)g(n)g(n)이 h(n)h(n)h(n)보다 느리다면, f(n)f(n)f(n)은 결국 h(n)h(n)h(n)보다도 느릴 수밖에 없다.
  예: f(n)=nf(n) = nf(n)=n, g(n)=n2g(n) = n^2g(n)=n2, h(n)=n3h(n) = n^3h(n)=n3 → 결국 f(n)∈O(n3)f(n) \in O(n^3)f(n)∈O(n3).

---

한 줄 요약

1. 계수 법칙: 상수 곱해도 상관없다.
2. 합의 법칙: 큰놈이 다 먹어버린다.
3. 다항 법칙: 제일 높은 차수만 남는다.
4. 곱의 법칙: 곱하면 시간복잡도도 곱해진다.
5. 전의 법칙: 중간단계 뛰어넘고 큰놈만 보면 된다.