算法拾遺

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 };

}

}