2. Devide & Conquer

2.1 Divide and Conquer Approach

• Binary Search Algorithm Design

• Points of observation

*

• Worst-Case Time Complexity

Binary Search 의 최악의 경우의 수를 알아보자

• Case1

• Case 2

n/2에 같이 있는  기호는 그 수보다 크지 않은 가장 큰 정수이다.

* n이 짝수일때 

*n이 홀수 일때 결론이 같다

2.2 MergeSort

• Worst_case Time Complexity : MergeSort

• Space Complexity Analysis

2.3 Master Theorem

• Auxiliary Master theorem

2.4 QuickSort

• Every-Case Time Complexity (Partition)

• Worst-Case Time Complexity (Quicksort)

• Average-Case Time Complexity(Quicksort)

2.5 Strassen's Algorithm

• Matrix Multiplication

• nxn Matrix : Strassen's Method

n=2

n일때

A의 원소가 꼭 원소일 필요없음 행렬이여도 적용이 된다.

• Strassen's Algorithm

• Average-Case Time Complexity Analysis of Number of Multiplications (Strassen)

7번의 곱셈

• Average-Case Time Complexity Analysis of Number of Additions/Subs (Strassen)

18번의 덧셈과 뺄셈

• 비교해보자

• 결론