1. 首頁 > 生活經驗 > >

Pascal 怎么計算時間復雜度 怎樣計算算法時間復雜度

知識經驗


Pascal 怎么計算時間復雜度 怎樣計算算法時間復雜度

文章插圖
大家好,小跳來為大家解答以上的問題 。怎樣計算算法時間復雜度，怎么計算時間復雜度(Pascal)這個很多人還不知道,現在讓我們一起來看看吧！
1、一個算法執行所耗費的時間 ， 從理論上是不能算出來的，必須上機運行測試才能知道 。
2、但我們不可能也沒有必要對每個算法都上機測試 ， 只需知道哪個算法花費的時間多 ， 哪個算法花費的時間少就可以了 。
3、并且一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多 。
【Pascal 怎么計算時間復雜度 怎樣計算算法時間復雜度】4、一個算法中的語句執行次數稱為語句頻度或時間頻度 。
5、記為T(n) 。
6、一般情況下，算法的基本操作重復執行的次數是模塊n的某一個函數f（n），因此，算法的時間復雜度記做：T（n）=O（f（n）） 。
7、隨著模塊n的增大，算法執行的時間的增長率和f（n）的增長率成正比，所以f（n）越?。?算法的時間復雜度越低，算法的效率越高 。
8、在計算時間復雜度的時候，先找出算法的基本操作，然后根據相應的各語句確定它的執行次數 ， 再找出T（n）的同數量級（它的同數量級有以下：1，Log2n ，n，nLog2n ，n的平方，n的三次方 ， 2的n次方，n?。?nbsp;， 找出后，f（n）=該數量級，若T(n)/f(n)求極限可得到一常數c，則時間復雜度T（n）=O（f（n）） 。
9、按數量級遞增排列，常見的時間復雜度有：常數階O(1),對數階O(log2n),線性階O(n),線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),... ， k次方階O(n^k), 指數階O(2^n)。
10、隨著問題規模n的不斷增大 ， 上述時間復雜度不斷增大，算法的執行效率越低 。
11、舉幾個具體的例子：1.for i:=1 to 100 do for j:=1 to 100 do s[i,j]:=0;執行次數100*100次，時間復雜度O(1)2.for i:=1 to n do for j:=1 to 200 do s[i,j]:=0;執行次數n*200次，時間復雜度O(n)2.for i:=1 to n do for j:=1 to n div 2 do s[i,j]:=0;執行次數n*n/2次，時間復雜度O(n^2)3.for i:=1 to n do for j:=1 to n-1 do for k:=1 to n-2 do s[i,j,k]:=0;執行次數n*(n-1)*(n-2)次 ， 時間復雜度O(n^3)4.for i:=1 to n dobeginfor j:=1 to n do s[i,j,0]:=0;for j:=1 to n do for k:=1 to n do s[i,j,k]:=1;end;執行次數n*(n+n*n)次 ， 時間復雜度O(n^3)——百度知道團隊pas世界歡迎你加入！ 。
本文到此分享完畢，希望對大家有所幫助 。