Algorithm_Week_2~3

탐색 문제 2의 최적성

이진 탐색(반으로 쪼개서 계속 탐색하는 방법) 의 경우, n = 2^k 로 가정하면
T(n) = 1+T(n/2)
= 1 + (1+T(n/4)) = 1+1+(1+T(n/8))
= 1 + ... + 1 + T(n/2k) = k + 1 = O(log n)번 비교( n = 2^k 이면 당연히 log n = k이다. 이때 log는 밑이 10이 아니라, 2인데 컴퓨터는 2진수를 쓰기 때문에 당연히 밑이 2인 log이다.)

=> 반으로 나눠서 한번 탐색하고, 크고 작은지 판별한 다음, 다시 반으로 나누고 탐색하고 반복하는 과정.

이 때 Big O 란?

빅오 표기법(Big O notation)이란 쉽게 이야기하면 알고리즘이 얼마나 빠른지 표시하는 방법이고, 또한 최악의 경우에 대해 표시한 것이다.

[출처] 빅오 표기법(Big O notation)이란?|작성자 개발하는 양토리

함수의 증가

• 우리 알고리즘이 입력이 n개 주어졌을 때, 답을 구하는데 걸리는 연산의 개수를 함수 f(n)으로 표현하자.

• 정의상, f(n)은 자연수에 대해 정의된 함수이다.

• 또, f(n)은 증가함수일 것이다.

• 그렇다면, f(n)이 n이 증가함에 따라 얼마나 빨리 커지는지를 아는 것은 알고리즘의 성능을 평가하는데 중요하다.

• f(n) = O(g(n)) :
  for all n ≥ n0 , f(n) ≤ cg(n) for some constant c.
  - 어느 값 이상부터는 모든 n에 대해서 f(n)의 값은 g(n)의 몇배보다 항상 작다는 말. 예를 들면 100x 와 x^2을 보면, x가 100이기 전 까지는 100x가 크지만 100 이후로부터는 x^2가 훨씬 크다. 따라서 함수의 증가 속도가 중요하지, 함수에 몇배를 곱했냐는 덜 중요하다.
  

• f(n) = Ω(g(n))
  for all n ≥ n0 , f(n) ≥ cg(n) for some constant c.
  - g(n)의 상수배보다, f(n)이 어떤 시점부터는 빠르게 증가한다. => 내가 알고싶은 것은 함수가 증가하는 속도인거지, 정확한 증가는 별로 원하지 않기 때문에. 미라가 6000년 전의 미라라면, 5998년 전 미라나 이런건 안중요함. 그냥 오래됐다는게 중요.

• f(n) = Θ(g(n))
  f(n) = O(g(n)) 인 동시에 f(n) = Ω(g(n))
  - f(n)과 g(n)이 증가하는 속도가 같다.

❖ g(n) = O(f(n)) ⇒ g 는 f 보다 빠르게 증가하지 않는다

❖ 주의: 위와 같이 정의되었음에도, f(n) = Θ(g(n)) 대신
O(g(n))이라고 쓰기도 함.

점화식의 이해

• 고등학교 교과 과정에서 배운 수열의 귀납적 정의와 유사함

• 점화식을 푸는 법

  • 반복 대치
    • 주어진 조건을 이용하여, 점점 작은 함수로 반복하여 대치하는 방법
    • 침착하게 꼼꼼히 풀자
  • 추정후 증명
    • 점화식의 결론을 추정하고, 수학적 귀납법을 이용하여 증명해감
    • 처음에 답을 가정하고 시작하는건데, 답을 잘 찍기가 쉽지 않음.
  • 마스터 정리
    • 주어진 점화식에 대해서 공식을 통하여 풀 수 있음
    • 이 강의에서는 다루지 않음.

반복 대치의 예(1)

• T(n) = T(n-1) + n, T(1) = 1
  풀이 : T(n-1) = T(n-2) + n-1, T(n-2) = T(n-3) + n-2… 를 이용
  T(n) = T(n-1) + n
  = (T(n-2) + n-1) + n
  = ((T(n-3) + n-2) + n-1) + n
  = ….
  = T(1) + 2 + 3 + … + n
  = n(n+1)/2 = Θ(n2)

반복 대치의 예(2)

• T(n) = 2T(n/2) + n, T(1) = 1
  풀이 : T(n/2) = 2T(n/4) + n/2, T(n/4) = 2T(n/8) + n/4…
  n = 2k (k = log2n)라고 가정
  T(n) = 2T(n/2) + n
  = 2{2T(n/4) + n/2} + n
  = 4T(n/4) + n + n
  = …
  = 2kT(n/2k) + kn
  이때, k가 밑이 2인 log n이라고 했을 때, n log n + n 이 되는데, 이는 2n log n보다는 작고 n log n보다는 크기때문에, Θ(n log n) 이다
  = Θ(n log n)