演算法並列

1. 如何計算一個演算法的時間復雜度

求解演算法的時間復雜度的具體步驟是： ⑴找出演算法中的基本語句； 演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。 ⑵計算基本語句的執行次數的數量級； 只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。 ⑶用大Ο記號表示演算法的時間性能。 將基本語句執行次數的數量級放入大Ο記號中。 如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。例如： for(i=1;i<=n;i++)x++;for(i=1;i<=n;i++) for(j=1;j<=n;j++)x++;第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個演算法的時間復雜度為Ο(n+n2)=Ο(n2)。 常見的演算法時間復雜度由小到大依次為： Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)Ο(1)表示基本語句的執行次數是一個常數，一般來說，只要演算法中不存在循環語句，其時間復雜度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間，而Ο(2n)和Ο(n!)稱為指數時間。計算機科學家普遍認為前者是有效演算法，把這類問題稱為P類問題，而把後者稱為NP問題。 這只能基本的計算時間復雜度，具體的運行還會與硬體有關。