Lecture 3

• Asymptotic Notation 점근적 표기법

  

  • O → tight upper bound 상한선 : 이것보다 클 수 없어! 같아도 됨**(2n^2 = O(n^2))**

    • n ≥ n0를 만족하는 n0와 양수c에 대하여 f(n) ≤ cg(n)을 만족하면 → f(n) = O(g(n))
    • f(n)이 g(n)보다 아래or같은 선상에 있으면 성립

  • Ω → tight lower bound 하한선 : 이것보다 작을 수 없어! 같아도 됨

    • n ≥ n0를 만족하는 n0와 양수c에 대하여 f(n) ≥ cg(n)을 만족하면 → f(n) = Ω(g(n))
    • f(n)이 g(n)보다 위or같은 선상에 있으면 성립

  • Θ → same : 계수값의 차이만 있는 것(최고차항)

    • n ≥ n0를 만족하는 n0와 양수c1, c2에 대하여 c1g(n) ≤ f(n) ≤ c2g(n)을 만족하면 →

      f(n) = Θ(g(n))

  • o → loose upper bound 상한선 : 이것보다 클 수 없어! 같으면 안됌**(2n^2 ≠ o(n^2))**

    • n ≥ n0를 만족하는 n0와 양수c에 대하여 f(n) < cg(n)을 만족하면 → f(n) = o(g(n))
    • f(n)이 g(n)보다 아래에 있으면 성립

  • w → loose lower bound 하한선 : 이것보다 작을 수 없어! 같으면 안됨

    • n ≥ n0를 만족하는 n0와 양수c에 대하여 f(n) > cg(n)을 만족하면 → f(n) = w(g(n))
    • f(n)이 g(n)보다 위에 있으면 성립

  • 성질

    • f(n) = O(f(n)), Ω(f(n)), Θ(f(n)) 이다.
    • f(n) = Θ(g(n)) → g(n) = Θ(f(n))
    • f(n) = O(g(n)) → g(n) = Ω(f(n)) (위치관계를 생각해보자!)
    • f(n) = o(g(n)) → g(n) = w(f(n)) (위치관계를 생각해보자!)
    • f(n) = Θ(g(n)), g(n) = Θ(h(n)) → f(n) = Θ(h(n))

  • 주의할점

    

    n = O(n^2) = O(n^3)인 것처럼 점근적 표기법은 집합임

    • O(n^3)안에 n^2, n^3+123n, 2135n +31 등등의 함수가 들어가 있는 개념임

  • Floors and ceilings 바닥과 천장

    • Floors바닥 : x를 넘지 않는 가장 큰 정수 → 내림(바닥? 아래에 있으니까 내려)
    • Ceiling천장 : x를 넘는 가장 큰 정수 → 올림(천장? 위에 있으니까 올려)

    

    기호 확인 잘하기!

  • 참조

    • n! ≤ n^n → O(n^n)
    • n! = o(n^n)
    • n! = w(2^n)
    • lg(n!) = Θ(nlgn)

Lecture 4~5

• Recurrences 점화식

  • T(n) = Θ(n) (n = 1)

               **2T(n/2) +  Θ(n) (n >1)**
    

    • 점화식을 해결하는 3가지 방법 : substitution 치환, recursion tree 재귀트리, master method 마스터 이론

  • Substitution Method 치환법

    • 수학적 귀납법을 사용
      • 초기의 값(n이 1,2정도)이 성립함을 보임
      • n < k 일때 성립한다고 가정하고, n = k일때 성립함을 보임
        • 그렇게 되면 1부터 모든 수에 대해서 성립함을 보일 수 있게 되므로 증명 가능!

  • Recursion Tree Method 재귀트리방법

  뒤에 달린  **Θ(n^2) = 밑의 그림에서 cn^2**은 deviding, combining과 같은 cost이다.

언제까지 내려가나? 길이를 m이라 해보자.

• T(n) → T(n/4) → T(n/16) → … → T(1) ⇒ (n/4^m = 1) ⇒ m = log4n (왼쪽 길이에서 확인가능)

• 언밸런스한 경우

이 경우에 길이는 더 오래 분리되는 곳 → 즉 나눠지는 비율이 더 큰 쪽이 더 길게 유지되므로 그 길이를 계산해주면됨 → 이 그림에서는 2/3 이므로 길이는 log3/2 n (비율을 역수취해서 밑으로 넣어버리면 됨)

• Master Method

  • T(n) = aT(n/b) + f(n)

  이론 4.1장에 의하면,

더 쉽게 요약한 것은 다음과 같다.

그 외에도 f(n)이 log형태일때 이론도 구글에 찾아보면 나와있으니 참고!

Q&A 세션 2주차 내용! 참고

• F(n), G(n) 사이의 빅오, 빅오메가, 빅세타의 관계를 물어봤을 때, 함수를 직접 그려보는 것이 편할 수도 있다!

• Tight bound : 점근선을 포함하는

  loose bound : 점근선을 포함하지 않는

• Prove or Disprove : 참임 or 참이 아님을 증명하라! counter example 만으로는 증명이 불가능함.

  ex) 4+ 2n + 3n^2 ∈ O(n^2) → 4+2n+3n^2 < 4n^2+2n^2+3n^2 = 9n^2 따라서 포함된다.

• 빅오, 빅오메가, 빅세타는 함수들의 집합임.

  O(n^2)에는 n^2, 9n+1, 3n^2+4n 등등 다양한 함수가 포함되어있는 것 처럼

• 1+1/2+1/3 + … + 1/n = logn

  why? 1~n까지 1/n 시그마한 것인데 이는 1~n까지 1/x dx 적분한 것 과 같기에 logn이 된다.