Desperate Undergraduate!Desperate Undergraduate!

예를 들어 생각해 보면, "1, 2, 3, 4, 5, 6, 7, 8, 9"에서 9를 찾는다고 가정해 보자. 각 Step 마다 n/2 만큼 감소하게 된다. 수식으로 표현해보면 Worst Case의 Time Complexity는 w(n) = w(2/n) + 1 이 된다. 이것은 w(n) = w(2/2^2) + 2 가 되고 다음은 w(n) = w(2/2^3) + 3 형태가 된다. n을 2^x 로 놓으면 w(n/2^x) + x 에서 w(n) = w(2^x/2^x) + logn 이 된다. w(2^x / 2^x)는 1이 되고 결국 1 + logn 이 된다. 그래서 System Stack Deapth는 1 + logn 이 된다.

피보나치 수열에서 알고리즘의 접근은 Sequential Approach와 Divide and Conquer Approach가 있었다. 이 방법에서 Divide and Conquer Approach가 Sequential Approach 보다 효과적이지 못하다는 것을 배웠다. 그러면 우리는 이 문제에 대해 일반화 시킬 수 있을까? 그것이 첫 번째 숙제이다.

My Solution)
두 가지 접근 방법이 있다고 가정하자. 하나는 Sequential Approach이고 다른 하나는 Divide and Conquer Approach이다. 우리의 목표는 집합에서 원소를 찾는 문제와 피보나치 수열 문제를 통해 일반화된 요약을 도출하는 것이다.

집합 : 유한 원소를 다룬다.
피보나치 수열 : 재귀 형태로 미지수 x에 따라 값이 변화한다.

Domain이 지정되어 있다면 Divide and Conquer Approach가 Sequential Approach보다 효율적이고, Domain이 지정되어 있지 않다면 Sequential Approach가 Divide and Conquer Approach보다 효율적이다.

Instructor's Solution)
하위 문제가 Overlapping이 많이 발생하는 경우, 분할 정복 접근보다는 순차접근이 효과적이다.

결과 : B