31251 Lecture Notes - Lecture 4: Binary Logarithm
30 Jun 2018
School
Department
Course
Professor
Divide and Conquer
• The general framework for a divide-and-conquer algorithm is:
1 Divide the instance into a set of subproblems.
2 If a subproblem is small enough, solve it, otherwise recursively split the subproblem.
3 Combine the subproblem solutions into a whole solution.
How to make it work?
• A problem has to be recursively similar – can an instance be broken up into smaller instances of
the same problem?
• The number and size of the subproblems must be in the right balance – this depends on the
“simple” solution’s complexity.
• We must be able to recombine subsolutions into a solution efficiently.
Example 1
• Binary Search – find if an element is in a sorted array (probably the simplest d&c algorithm):
1 Check the middle of the array, is the middle greater or smaller than the target element?
2 If it’s the same, you’ve found it! If the array is size one and it’s not the same, it’s not there!
3 If it’s greater, search the left side of the array. Otherwise search the right.
• O(log n) time.
Example 2
Fast exponentiation – calculate x n for large n:
Function exp(x,n)
if n == 0 then
return 1;
end
if n is odd then
return x × exp(x, n − 1);
end
else x 0 = exp(x, n 2 );
return x 0 × x 0;
;
end
• If we use D&C multiplication, and |x| = m, Θ(mlog2 3n log2 3 )
1 | P a g e
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Divide and conquer: the general framework for a divide-and-conquer algorithm is: 1 divide the instance into a set of subproblems. 2 if a subproblem is small enough, solve it, otherwise recursively split the subproblem. 3 combine the subproblem solutions into a whole solution. Simple solution"s complexity: we must be able to recombine subsolutions into a solution efficiently. Example 1: binary search find if an element is in a sorted array (probably the simplest d&c algorithm): 2 if it"s the same, you"ve found it! If the array is size one and it"s not the same, it"s not there! 3 if it"s greater, search the left side of the array. Otherwise search the right: o(log n) time. Fast exponentiation calculate x n for large n:
