Divide and Conquer 实例
程序员文章站
2022-06-02 11:53:06
...
Algorithm Design Techniques - 2
##Divide and Conquer##
note:
Divide
: smaller problem are solved recursively (except base cases)
Conquer
: The solution to the original problem is then formed from the solutions to the sub-problems.
###Cases solved by divide and conquer###
- The maximum sub-sequence sum – the O( N log N ) solution
- The maximum sub-sequence sum – the O( N log N ) solution
- Merge-sort and quick-sort – O( N log N )
###Running Time of Divide and Conquer Algorithms###
merge-sort : a = b = 2; p = 0 and k = 1; ---> T = O(N*logN)
####Closest Points Problem####
问题描述: 平面上有n个点,找到距离最短的两个点。
<!-- lang: cpp -->
/* points are all in the strip */
for ( i=0; i<NumPointsInStrip; i++ )
for ( j=i+1; j<NumPointsInStrip; j++ )
if ( Dist( Pi , Pj ) < min )
min = Dist( Pi , Pj );
/* points are all in the strip */
/* and sorted by y coordinates */
for ( i = 0; i < NumPointsInStrip; i++ )
for ( j = i + 1; j < NumPointsInStrip; j++ )
if ( Dist_y( Pi , Pj ) > min )
break;
else if ( Dist( Pi , Pj ) < min )
min = Dist( Pi , Pj );
####The Selection Problem####
####Multiplying Integers####
####Matrix Multiplication####
转载于:https://my.oschina.net/zjuysw/blog/190828