최대 1 분 소요

  • input size가 아주 커질 때 가정(n→ $\infin$)
  • notation

    • $O$ : Upper Bound, Worst Case

      O(g(n)) = {f(n) 모든 n > $n_0$에서 0 ≤ f(c) ≤ cg(n)를 만족하는 positive constant인 $n_0$와 c가 존재}

    • $\Omega$ : Lower Bound, Best Case

      O(g(n)) = {f(n) 모든 n > $n_0$에서 0 ≤ cg(n) ≤ f(c) 를 만족하는 positive constant인 $n_0$와 c가 존재}

    • $\theta$ : Upper Bound & Lower Bound,

      O(g(n)) = {f(n) 모든 n > $n_0$에서 0 ≤ $c_1$g(n) ≤ f(c) ≤ $c_2$g(n)를 만족하는 positive constant인 $n_0$와 c가 존재}

Untitled

  • 특징

    Untitled

  • comparing

    Untitled

  • 예시

    • Insertion Sort

      Untitled

      • complexity
        • best case : $O(n)$
        • worst case : $O(n^2)$