時間復(fù)雜度の計算：

first先算出一個程序總共運(yùn)行的次數(shù)T(n)

例如：

? ??? ? ① ② ④

? ????? ↑? ? ?↑? ? ↑

for(int i=0;i<n;i++)

{

cout<<i<<”?”<<”gjy”;→③
?}

return 0;→⑤

①變量i初始化，運(yùn)行一次

②判斷條件，符合（此處為i<n）運(yùn)行n次，不符合（此處為i==0）運(yùn)行1次

③輸出運(yùn)行n次

④每次輸出之后i自增1，運(yùn)行n次

⑤return 0;語句運(yùn)行一次

共計3n+3次。

second判斷復(fù)雜度

①如果運(yùn)行次數(shù)為常數(shù)，那么時間復(fù)雜度為O(1)

②如果是單層循環(huán)，就比如T(n)=3n+3，前面的三看成一，后面的三忽略不計，時間復(fù)雜度為O(n)

③T(n)為多項式，保留次數(shù)最高的一項，如T(n)=5n3+6n2+n，這里面取5n3來計算，5看成1去掉，所以其復(fù)雜度為O（n3） *鏡易理解法：在大部分循環(huán)范圍在1~n區(qū)間的循環(huán)有幾重就是O(n的幾次方)，當(dāng)然，這種方式不一定適用于所有情況

總結(jié)：T(n)是不是常數(shù)

· 是：時間復(fù)雜度為O(1)

· 否:時間復(fù)雜度為O(保留T(n)的最高次項并且去掉最高次數(shù)的系數(shù))

?

名稱??時間復(fù)雜度

?常數(shù)時間O(1)

對數(shù)時間O(log n)

線性對數(shù)時間O(n)

二次時間O(n log n)

三次時間O(n2)

指數(shù)時間O(n3)

線性時間O(2^n)

?