時(shí)間復(fù)雜度的計(jì)算-資料下載頁(yè)
2025-05-16 05:51本頁(yè)面
【正文】 for(k=1。k=j。k++)(5) x++。 該程序段中頻度最大的語(yǔ)句是(5)，內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問(wèn)題規(guī)模n沒(méi)有直接關(guān)系，但是卻與外層循環(huán)的變量取值有關(guān)，而最外層循環(huán)的次數(shù)直接與n有關(guān)，因此可以從內(nèi)層循環(huán)向外層分析語(yǔ)句(5)的執(zhí)行次數(shù)：則該程序段的時(shí)間復(fù)雜度為T(n)=O(n3/6+低次項(xiàng))=O(n3)。（4）算法的時(shí)間復(fù)雜度不僅僅依賴于問(wèn)題的規(guī)模，還與輸入實(shí)例的初始狀態(tài)有關(guān)?！纠?．12】在數(shù)值A(chǔ)[0..n1]中查找給定值K的算法大致如下：(1)i=n1。 (2)while(i=0amp。amp。(A[i]!=k)) (3) i。 (4)return i。 此算法中的語(yǔ)句(3)的頻度不僅與問(wèn)題規(guī)模n有關(guān)，還與輸入實(shí)例中A的各元素取值及K的取值有關(guān):①若A中沒(méi)有與K相等的元素，則語(yǔ)句(3)的頻度f(wàn)(n)=n；②若A的最后一個(gè)元素等于K,則語(yǔ)句(3)的頻度f(wàn)(n)是常數(shù)0。（5）最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度 最壞情況下的時(shí)間復(fù)雜度稱最壞時(shí)間復(fù)雜度。一般不特別說(shuō)明，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度。 這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界，這就保證了算法的運(yùn)行時(shí)間不會(huì)比任何更長(zhǎng)?！纠?．19】查找算法【例18】在最壞情況下的時(shí)間復(fù)雜度為T(n)=0(n)，它表示對(duì)于任何輸入實(shí)例,該算法的運(yùn)行時(shí)間不可能大于0(n)。 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。 常見(jiàn)的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)0(1)、對(duì)數(shù)階0(log2n)、線形階0(n)、線形對(duì)數(shù)階0(nlog2n)、平方階0(n2)立方階0(n3)、…、k次方階0(nk)、指數(shù)階0(2n)。顯然，時(shí)間復(fù)雜度為指數(shù)階0(2n)的算法效率極低，當(dāng)n值稍大時(shí)就無(wú)法應(yīng)用。 類似于時(shí)間復(fù)雜度的討論，一個(gè)算法的空間復(fù)雜度(Space Complexity)S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它也是問(wèn)題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡(jiǎn)稱為空間復(fù)雜度。算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1