求時間複雜度

1樓：蠢到讓你受傷

1、如何計算演算法的時間複雜度

在計算演算法時間複雜度時有以下幾個簡單的程式分析法則:

1.對於一些簡單的輸入輸出語句或賦值語句,近似認為需要o(1)時間

2.對於順序結構,需要依次執行一系列語句所用的時間可採用大o下"求和法則"

求和法則:是指若演算法的2個部分時間複雜度分別為 t1(n)=o(f(n))和 t2(n)

=o(g(n)),則 t1(n)+t2(n)=o(max(f(n), g(n)))

特別地,若t1(m)=o(f(m)), t2(n)=o(g(n)),則 t1(m)+t2(n)=o(f(m) + g(n))

3.對於選擇結構,如if語句,它的主要時間耗費是在執行then字句或else字句所用

的時間,需注意的是檢驗條件也需要o(1)時間

4.對於迴圈結構,迴圈語句的執行時間主要體現在多次迭代中執行迴圈體以及檢驗

迴圈條件的時間耗費,一般可用大o下"乘法法則"

乘法法則: 是指若演算法的2個部分時間複雜度分別為 t1(n)=o(f(n))和 t2

(n)=o(g(n)),則 t1*t2=o(f(n)*g(n))

5.對於複雜的演算法,可以將它分成幾個容易估算的部分,然後利用求和法則和乘法

法則技術整個演算法的時間複雜度

另外還有以下2個運演算法則:

(1) 若g(n)=o(f(n)),則o(f(n))+ o(g(n))= o(f(n))

(2) o(cf(n)) = o(f(n)),其中c是一個正常數

可以用以上法則對下面程式段進行簡單分析

①for (i=0; i

② for (j=0; j

第①條與②③④⑤是迴圈巢狀t1(n)*t2(n)* (t3(n)+ t4(n)* t5(n))= o(n*n*n)

即為整個演算法的時間複雜度

o(1)

2樓：宛丘山人

t=o(n)

什麼是時間複雜度空間複雜度

1 時間複雜度是指執行演算法所需要的計算工作量。時間複雜度是一個函式，它定性描述了該演算法的執行時間。這是一個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述，不包括這個函式的低階項和首項係數。2 空間複雜度是指執行這個演算法所需要的記憶體空間。空間複雜度需要考慮在執行過程中為區域...

時間複雜度的定義，C 中時間複雜度是什麼意思

1 時間複雜度 1 時間頻度 一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機執行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數...

求時間複雜度for i 2 in ifor j 2 ji 1jx a x為什麼是 n 1 n

i從2到n變化，共 n 1詞迭代，j從2到i 1變化，共i 2次迭代 所以共有0 1 2 n 2 n 1 n 2 2 下面程式段的時間複雜度是 for i 1 i n i for j 1 j 雙重for迴圈，當然就是n的平方了，故選擇d x 0 for i 1 i i 1時 迴圈n 1 i 2。n ...