如果算法里面只有加減法，則算法時(shí)間算加減法的次數(shù)。
如果算法里面包含加法和乘法，則算法時(shí)間一般只算乘法次數(shù)，因?yàn)橛?jì)算機(jī)計(jì)算加減法很快，可忽略。

問(wèn)題：什么是好的算法？

一個(gè)程序的運(yùn)行時(shí)間，依賴與算法的好壞和問(wèn)題的輸入規(guī)模，問(wèn)題的輸入規(guī)模是指輸入量的多少。

算法效率

• 最壞情況復(fù)雜度$T_{worst(n)}$
• 平均復(fù)雜度$T_{avg}(n)$

$$T_{avg(n)}\le T_{worst}(n)$$
除非特別指定，一般關(guān)心最壞情況的復(fù)雜度。

問(wèn)題：怎么分析算法的復(fù)雜度？

不計(jì)循環(huán)索引的遞增和循環(huán)終止條件、變量聲明、打印結(jié)果等操作。

測(cè)定運(yùn)行時(shí)間的方法：計(jì)算對(duì)運(yùn)行時(shí)間由消耗的基本操作的執(zhí)行次數(shù)。運(yùn)行時(shí)間與這個(gè)計(jì)數(shù)成正比。

分析算法的運(yùn)行時(shí)間：把基本操作的數(shù)量與輸入規(guī)模關(guān)聯(lián)起來(lái)，即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)。

判斷一個(gè)算法的效率時(shí)，函數(shù)中的常數(shù)和其他次要項(xiàng)常常可以忽略，而更應(yīng)該關(guān)注主項(xiàng)（最高階項(xiàng)）的階數(shù)。

只需要關(guān)注隨著處理的數(shù)據(jù)的規(guī)模的增大，算法復(fù)雜度的增長(zhǎng)趨勢(shì)。

在進(jìn)行算法分析時(shí)，語(yǔ)句總的執(zhí)行次數(shù)$T(n)$是關(guān)于問(wèn)題規(guī)模n的函數(shù)，進(jìn)而分析$T(n)$隨n的變化情況并確定$T(n)$的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度，記作：$T(n)=O(f(n))$。它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和$f(n)$的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度。其中$f(n)$是問(wèn)題規(guī)模n的某個(gè)函數(shù)。

推導(dǎo)大O階方法：

用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。

在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。

如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)。

得到的結(jié)果就是大O階。

時(shí)間復(fù)雜度的漸進(jìn)表示法

• $T(n)=O(f(n))$表示存在常數(shù)$C>0$，$n_0>0$使得當(dāng)$n\ge n_0$時(shí)有$T(n)\le C?f(n)$
• $T(n)=\Omega (g(n))$表示存在常數(shù)$C>0$，$n_0>0$使得當(dāng)$n\ge n_0$時(shí)有$T(n)\ge C?g(n)$
• $T(n)=\theta (h(n))$表示同時(shí)有$T(n)=O(h(n))$和$T(n)=\Omega (h(n))$成立

$O(f(n))$可有無(wú)數(shù)種表達(dá)方式，一般取最小的上界
$\Omega (g(n))$可有無(wú)數(shù)種表達(dá)方式，一般取最大的上界
空間復(fù)雜度和時(shí)間復(fù)雜度同理

時(shí)間復(fù)雜度分析小竅門

• 若兩段算法分別有復(fù)雜度$T_1(n)=O(f_1(n))$和$T_2(n)=O(f_2(n))$，則
  $T_1(n)+T_2(n)=max(O(f_1(n)),O(f(n)))$
  $T_1(n)+T_2(n)=O(f_1(n)\times f_2(n))$
• 若$T(n)$是關(guān)于n的k階多項(xiàng)式，則$T(n)=\theta (n^k)$
• 一個(gè)for循環(huán)的時(shí)間復(fù)雜度等于循環(huán)次數(shù)乘以循環(huán)體代碼的復(fù)雜度
• if-else結(jié)構(gòu)的復(fù)雜度取決于if的條件判斷復(fù)雜度和兩個(gè)分枝部分的復(fù)雜度，總復(fù)雜度取三者中最大
  
  
  

總結(jié)

以上是生活随笔為你收集整理的算法时间复杂度的渐进表示法 + 分析窍门的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。