Divide and Conquer

 

Divide - and - Conquer  ==> Top - down approach

 

binary search

• merge 과정이 필요 없는 가장 간단한 D&C
• recursion으로 구현할 수도 있는데, iteration으로 구현할 수도 있음
• tail - recursion (끝에서 계속 재귀호출)
• => stack overflow.. ==> iteration 버전을 쓰자.

merge sort

quick sort

 

 

 

Divide and Conquer - Design 

• Ex 흑석동 중앙대학교 -->  부산대병원 응급실 가기
• ==> Question : find the best path.
• ==> A problem ==> various solution approaches
• -->중앙대 --> 서울역 ktx --> 부산역 --> 택시 --> 부산대 병원 (이게 divide and conquer)
• 우리가 생각 할 수 있는 가장 기계적이고 단순하게 나누기

 

< Divide and Conquer Design > 

Step 1. Divide into >= 2 smaller problems(instances) - 두개이상의 작은 문제로 나누기 
Step 2. Solve each instance
Step 3: Combine the subsolutions (optional!)
-- 절대적인 설계 요소--

** How to solve the Step 2?
--> 1. recursively : divide and conquer.
--> 2. iteratively, sequentially. (if the subproblem is small) 

즉, step 2를 어떻게 풀든, 전체 Step 1,2,3을 밟는다면 D&C로 문제를 해결했다고 볼 수 있음

Q: how to solve the subproblems? ==> X
Q: Where is the detailed design on the subsolution? ==> X

=>의미 없음 위의 스텝이 이미 상세 솔루션을 포함하고 있는 것임

==> 나누어진 subprob를 어떻게 풀지는 전~~~혀 중요하지 않다.

 

 

Ex: sorted array S = [10 12 13 14 18 20 25 27 30 35 40]
Problem: Find x, locate x in S (searching)

 

==> D&C 로 풀어보자

D&C_Search(binary search)
if x = S[mid], return mid
Step 1: Divide S into 2 subarrays
  if x < S[mid], retrurn Left array, otherwise Right array
Step 2: Conquer(Solve) the chosen array
Step 3: Combine(Obtain) the solution(s)  ==> 이 문제에선 필요가 없음

---

x = 18,
10 12 13 14 18 20 25 27 30 35 40 (S[mid] = 20)
10 12 13 14 18 (return Left array, S[mid] = 13)
14 18 (return Right array, S[mid] = 14)
18(return Right array,  find the index)

Detailed ver.
D&C_Search(S, x, low, high) : S[low] ~ S[high]
if low > high, then return nill.
else
  mid = (low + high / 2)
  if x = S[mid], then return mid
  else if x < S[mid] then return D&C_Search(... low, mid-1)
  else  return D&C_Search(... mid+1, high)
  
  ---- 

D&C_A(original problem size)
...
divide(orig -> Left, Right)
solve D&C_A(Left information)
solve D&C_A(Right information)
combine(Left + Right) // optional
...
--> Top-down approaches, Natural design.

Divide and Conquer - Analysis

** How to solve the Step 2?
1. Recursion : concise(간략), natural, clear, 기계적 해법. (system call 계속 부름 => 느려진)
2. Iteration :  faster, save memory space. (system stack) 
--> recursion depth, stack depth : log(n) + 1.

(8개 있으면.. 한번 나누고, 44 두번나누고, 22 세번나누고 11 마지막에 찾으니까 +1) 
==> 결론적으로 subproblem이 작으면(== 우리가 쓰는 computer performance에 따라 결정), 반복 도는게 더 빠를 수도 있다.

 

** 탐색을 해결하는 다양한 방식 중 D&C를 따르는 방식이 binary search

Q: Time Complexity.
1. Best-case: O(1)
2. Worse-case: 1/2 size decreasing -> O(logn)
--> Mathematical analysis is required( 수학적 사고 ) 

 

TC(핵심?) = # of basic operations. 

 

T(n) = Divide + Conquer + Combine
      = ? + ? + 0 ( 방금 그 예제의 경우, step 3를 하지 않으므로)
      = 1(Divide는 step 1에서 한번만 이루어지고 step 2에서 다시 divide를 할 지 말 지 알 수 없으므로)  +
         T(n/2) or T(n/2) (왼쪽 또는 오른쪽)
==  1 + T(n/2) --> recurrence eqn.

T(n) = 1 + T(n/2) = 1 + 1 + T(n/4)
      = 2 + T(n/4) = 2 + 1 + T(n/8)
      = 3 + T(n/8) .....
      =  T(n/2^k) + k (suppose n = 2^k)
      = T(n/n) + logn
      = T(1) + log(n) ==> * T(1) == 1개짜리 element에서 찾는 worst case == 1
      = 1 + log(n) <= O(log(n))
       *** 1+log(n) <=  k * log(n)인 k가 존재하므로 이렇게 표시할 수 있고, 이 알고리즘은 O(logn)이라고 표시 가능

 

D&C: Merge Sort - Design

 

Q: Sorting with D&C -> design and analysis

<Design>
D&C_Sort(orig array)
Step 1: Divide into 2 >= subarrays
Step 2: Solve(Conquer) each subarray - sort Left, Right
Step 3: Combine the subsolutions - merge Left, Right

 

Example : insight from examples.
S = [27 10 12 20 25 13 15 22], n = 8
Step 1: Divide -> [27 10 12 20] [25 13 15 22]
                                    Left               Right
Step 2: Solve/Sort -> Left(10 12 20 27), Right(13 15 22 25) ==> do NOT care about the details.      
Step 3: Combine/Merge -> 10 12 13 15 20 22 25 27

Combine/merge(Left, Right)
Example: Left(10, 27), Right(12,20)
10 vs 12

-> 10

27 vs 12

-> 10 12

27 vs 20

-> 10 12 20

-> 10 12 20 27 

 

D&C_Sort(S[1..n]:array)
--------------------------------
if(n>1) // depending on your coding style.  --> 종료조건
copy S[1] ... S[mid] to Left array             //divide
copy S[mid + 1] ... S[n] to Right array    // divide
D&C_Sort(Left array)                           //conq.
D&C_Sort(RIght array)                        // conq.
Combine/merge(Left array, Right array)           // combine
---------------------------------

* D&C: natural top-down systematic + termination conditions(종료조건 반드시 설정 => recursion 떄문에)

 

 

Merge Sort - Analysis 

log(n) -> nlog(n) (직관적, 한번 내려가는데 log n 인데 이걸 다시 n회 동안 비교하고 합쳐야함) 

• Example: Left(10, 27), Right(12,20)
• log n번 분해 했다가 양 옆에 다시 하나씩 비교하면서 합치기 => n개니까 n번만큼 비교 필요 (대충)

T(n) : Time complexity

T(n) = divide + conquer + combine ( 각 basic operation을 구하는 것!!! => 누가 어디서 하든 반드시 있는 거)

      =  ? + solve Left(T(n/2) + solve Right(T(n/2) + combine
      = ? + 2*T(n/2) + n/2 + n/2 - 1
      (** Example: Left(10, 27), Right(12,20) 각 개수만큼 pair로 비교하다가 마지막 하나 남은건 그냥 내림)

      = ? + 2*T(n/2) + n -1
      = 0 + 2*T(n/2) + n -1 
       (**  왜 divide 0? => 사실 divide 할 떄 copy하지 않고, 그냥 바로 나눠서 sort 가능(코드적으로)  => 반드시 필요 x

       (basic operation이 아니라는 소리다.)

      = 2T(n/2) + n -1 (recurrence equation)
      <= 2T(n/2) + n (upper bound에 관심, 빼기는 필요 없음  ==> 적어도 얼만큼의 performance를 낼 수 있냐가 중요. )
       = 2(2T(n/4) + n/2)) + n = 4T(n/4) + 2n
       = 8T(n/8) + 3n ....
       = 2^k * T(n/2^k) + k*n  (trick: n = 2^k  ==> n은 아주 큰수라고 가정)
       = n * T(n/n) + logn *n
       = n * T(1) + n*log(n) = n * log(n) ==> O(nlogn)
       (** T(1) == 하나짜리 element인 array를 sort할 필요 자체가 x, 즉 0이 된다.)

 

Quiz : k-way merge sort가 되었을 때, optimal k가 존재?
(일반적인 merge sort가 2-way => 반갈해서 나누고 합친다는 뜻)

Quiz :  2-way merge sort가 3-way merge sort보다 더 좋을까?

 

 

Divide & Conquer - Reccurences

- MIT 6.042J (Fall 2010) <Mathematics for computer Science> 듣기 ==> 심화학습
=> Lecture 1, 2, 3 => 꼭 보기 ( CS 증명의 중요성, 수학적 사고, 표현, 의사소통 수단)
=> Desired state can(NOT) be reachable from the start.
=> Proposition, Axiom -> logical deduction -> TRUE
=> Implication P ==> Q(T), Predicates
=> proof by contradiction, proof by induction
=> strong induction: if a problem seems to prove hard, 
=> make the problem stronger proposition -> easy to prove
=> invariants, lemma, theorem using 8 puzzle.

==> 이후에 Lecture 14: D&C Recurrences Equation
-> 하노이타워, merge sort
-> D&C Rec: general definition and solutions

 

Week 2.6 Thinking Habits in CS
=> indirect algorithm goal

 

 

D&C: Quick sort - Design

Question: D&C 에서  combining Step 없이 Sorting  가능?
-> D&C (without Step 3/Combininb)
-> combine 이 필요했다면 이름이 D&C&C가 됐을 것. => optional이란 뜻

 

ex) 15 22 13 27 12 10 25 
> (left part) (right part) : divide(step1)  ===> divide가 몹시 중요해짐
   (left) < (right) : 왼쪽과 오른쪽의 관계성이 확실해야 한다.

 ==> (left)     <     pivot 기준 : random(중간값으로 잡으면 중간값을 찾기가 더 어려움)     <     (right)
-> (left part sort) (right part sort) : conq. (step 2)
-> END. ( combine 하지 않는다 )

 

15 22 13 27 12 10 25 : pivot(15) => S[n]   ==> pivot을 기준으로 크고 작은걸 양 옆으로 나눈다.
left 15 right
-> divide
-> (13 12 10) 15 (22 27 20 25)
-> conq(not detailed)
-> 10 12 13 15 20 22 25 27

 

D&C_Sort(low, high: array index) --> Quick Sort.
{
if(high > low) // stopping condition, termination condition.
{
        pivotindex = Divide(low, high)
        D&C_Sort(low, pivotindex -1) //left
        D&C_Sort(pivotindex +1, high) //right
}}

 

D&C: Quick sort - Analysis

divide / partitioning Algo.
=> 피봇을 정해놓고 피봇보다 작은 값을 찾아서 피봇 근처에 모아 놓음
=> 2중 for문을 사용해서 
=> 마지막에 j 위치와 피봇 위치를 바꾸어주면, 다시 D&C로 나뉘는 문제

Question : Analysis? T(n)?

T(n) = Divide + Conq. + Combine
= ? + ? + ?
= (n-1) + T(n/2)+T(n/2) + 0 ==> Best case (피봇이 중간값이라는 보장x, 운좋게 중간값이면 좋은거)

( 왜 n-1 ? : pivot으로 정해진 값 빼고, n-1개의 element들을 한번씩 탐색 후 배치 )
<= 2T(n/2) +n (빼기는 필요 없음, upper bound에 관심)
= 2^k * T(n/2^k) + kn (2^k = n)
= nT(n/n) + logn*n = n*0 + n(logn) = n(logn) = O(nlogn)

 

==> 과정은 다르나 결과는 merge sort와 같다. (Best case)

 

T(n) = Divide + Conq. + Combine
= (n-1) + T(left) + T(right) + 0 --> Worst-case TC?
= (n-1) + T(n-1) + T(1) + 0
= T(n-1) + n-1
= T(n-2)+(n-2) + (n-1)
= T(n-3)+(n-3) +(n-2) +(n-1) 
....
= n(n-1)/2 <= O(n^2) (Worst case)

 

 

Recurrences - Part 2

•  Help you find promising approaches in the process of designing an algorithm with recurrences.

 

<Recurrences equations>
1. Describes a sequence of numbers
  - Early terms(numbers) are specified explicitly
  - later terms are calculated(expressed) a function of their predecessors.
  - Ex. T(1) = 1, T(n) = T(n-1) + 1.
2. Reduces a big problem into smaller problems until easy cases(terms) are reached.(progressively)
3. Useful and powerful to analyze the performance of recursive algorithms
  --> Time complexity analysis.

D&C == recurrence ? :  X 

 

Two big classes of recurrences in CS.

1. Linear recurrence
  : later terms = linear combination of early terms.(단순 곱, 합)
  : Linear Algebra

2. D&C recurrence

ex) 
<Fibonacci recurrence> 
f(0) = 1, f(1) = 1
f(n) = f(n-1) + f(n-2) : linear recurrence f(n) is a linear comb

<merge sort recurrence>
T(1) = 0
T(n) = 2T(n/2) + n-1  ==> not a linear comb. of preceding terms
-> NOT linear recurrence -> D&C recurrence
-> T(n) is a function of T(n/2)


Time complexity.
Fibonacci recurrence (linear recurrence)
T(n) = T(n-1) + T(n-2) --> O(2^n) : not tight bound
~ O(1.6180^n /sqrt(5)) : tight upper bound.  -> exponential TC. ==>  비용이 높다.

Mergesort recurrence (D&C recurrence)
T(n) = 2T(n/2) + n-1 --> T(n) ~ O(nlogn)


Observations -> Guidelines:

1. Generating smaller problems is more important to algorithmic speed(efficiency) than reducing the extra steps per recursive calls.
2. More generally, linear recurrences (have big subproblems) typically have Exponential solution(extremely inefficient) while D&C recurrences(have small subproblems) usually have solutions by a polynomial(지수함수가 아니라는 뜻) TC.
3.  If the subproblems are only a fraction of the size of the original, then the solution is typically bounded by a polynomial. --> D&C design is good.
4. Even worse, Fibonacci recurrences have subproblems "overlapped." -> Repeated calculations for the same terms are performed ->> extremely inefficient.
5. How to deal with Fibonacci?
  ==> We know that the recurrence can be implemented recursively as well as iteratively.
--> f0,f1,f2,f3,f4,f5
--> New design is introduced!! (4주차 Dynamic Programming)




==> D&C가 효율적일 때도 있고, DP가 효율적일 때도 있다.