這是一個遞歸調用因k的初值為由語句()知每次調用k增故第()語句執行n次()是FOR循環語句在滿足()的條件下執行該語句進入循環體()n次加上最後一次判斷出界故執行了n+次()也是循環語句當k=時判斷n+次(進入循環體()n次)k=時判斷n次最後一次k=n時判斷次故執行次數是(n+)+n+…+=(n+)(n)/次語句()是()的循環體每次比()少一次判斷故執行次數是n+(n)+…+=(n+)(n)/次注意分析時不要把()分析成n次更不是次
(這時i= s=) REPEAT語句先執行循環體後判斷條件直到條件為真時退出循環
算法在最好情況下即二進制數的最後一位為零時只作一次判斷未執行循環體賦值語句A[i]執行了一次;最壞情況出現在二進制數各位均為(最高位為零因題目假設無溢出)這時循環體執行了n次時間復雜度是O(n)循環體平均執行n/次時間復雜度仍是O(n)
該算法功能是將原單循環鏈表分解成兩個單循環鏈表其一包括結點h到結點g的前驅結點;另一個包括結點g到結點h的前驅結點時間復雜度是O(n)
第一層FOR循環判斷n+次往下執行n次第二層FOR執行次數為(n+(n)+(n)+…+)第三層循環體受第一層循環和第二層循環的控制其執行次數如下表
i= … n
j=n n n n … n
j=n n n n …
… … … …
j=
j=
j=
執行次數為(++…+n)+(++…+n)+…+n=n*n(n+)/n(n)/在n=時f()=執行過程中輸出結果為sum=sum=sum=sum=sum=(每個sum= 占一行為節省篇幅這裡省去換行)
O(n)m的值等於賦值語句m:=m+的運行次數其計算式為 ()O() ()O(n) ()O(n) ()O(n) ()O(n)
()由斐波那契數列的定義可得
Fn=Fn+Fn
=Fn+Fn
=Fn+Fn
=Fn+Fn
=Fn+Fn
……
=pF+qF
設Fm的執行次數為Bm(m=…n)由以上等式可知Fn被執行一次即Bn=;Fn被執行兩次即Bn=;直至F被執行p次F被執行q次即B=pB=qBm的執行次數為前兩等式第一因式系數之和即Bm=Bm+Bm再有Bn=和Bn=這也是一個斐波那契數列可以解得
Bm= [( )nm+( )nm+] (m=…n)
()時間復雜度為O(n)
從小到大排列為logn n/+logn n nlogn n+lognn nn+n n/ (/)n n!(n n)
[] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22749.html
