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