算法拾遗

1、贪心算法、动态规划、分治的区别

分治法经分解得到的子问题互相独立且与原问题相同；贪心算法并不从整体最优加以考虑，它所作出的选择只是在某种意义上的局部最优选择；动态规划算法经分解得到的子问题往往不是互相独立的。

2、NP问题

NP={L|L是一个在多项式时间内被一台NDTM所接受的语言}

3、时间复杂度的计算

时间复杂性：需要时间资源的量。

O(n)：如果存在正的常数C和自然数N0，使得当N>=N0时有f(N)<=Cg(N),则称函数当N充分大时上有界，且g(N),是它的一个上界。

4、Prim算法

//设有图连通带权图 G = ( V,E ) ：

void prim (int n,float [][] c)

{

T= {};

S= {1};

while( S!=V )

{

( i , j ) = i∈S && j ∈V-S 的最小权边;

T = T ∪ { ( i , j ) };

S = S ∪ { j };

}

}