欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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### Divide and Conquer 实例Divide and Conquer 实例Divide and Conquer 实例

merge-sort : a = b = 2; p = 0 and k = 1; ---> T = O(N*logN)

Divide and Conquer 实例

####Closest Points Problem####

问题描述: 平面上有n个点,找到距离最短的两个点。 Divide and Conquer 实例

<!-- 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