• 정리해야 할 것

  • 수도코드
  • 시간복잡도 (최선, 최악, 평균)
  • 사용된 알고리즘

• Sequential search vs Binary search

  • Sequential search

    S(n) = S(n+1) + 1 → 시간복잡도 N

  • Binary search

    S(n) = S(n/2) + 1 → 시간복잡도 logN : 정렬이 되어 있는 경우 유용

• Recurrence relation

  • 피보나치

    f(n) = f(n-1) + f(n-2)

  • n번째 피보나치

    • DP (bottom-up)

• quicksort의 W(n) → n제곱

• quicksort의 A(n) → nlogn

  • nA(n) - (n+1)A(n-1) = 2(n-1)

Divide-and-Conquer

2.5 슈트라센 알고리즘 - 행렬곱셈

for(i=1; i<=n; i++) {
	for(j=1; j<=n; j++) {
		C[i][j]=0;
		for(k=1; k<=n; k++)
			C[i][j] = C[i][j] + A[i][k]*B[k][j];
	}
}

• 곱: 8 →(-1)→ 7
• 합: 4 →(+14) → 18

→ 더하기보다 곱하기가 cost가 세다

• T(n) = 7T(n/2)