演算法導論時間復雜度

㈠ 演算法時間復雜度計算

首先假設任意一個簡單運算的時間都是1，例如a=1;a++;a=a*b;這些運算的時間都是1.

那麼例如
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
a++; //注意，這里計算一次的時間是1.
}
那麼上面的這個例子的時間復雜度就是 m*n

再例如冒泡排序的時間復雜度是N*N；快排的時間復雜度是log(n)。

詳細的情況，建議你看《演算法導論》，裡面有一章節，具體講這個的。

㈡ 最優合並問題的時間復雜度怎麼算

一般來說, 標準的分治法合並排序時間復雜度為O(n * lg n), 略小於插入排序的O(n*n), 遞歸式的時間復雜度求解方法比較多,有畫圖分析法, 算式求解即類似於 T(n) = f(T(n-1))的求解方法, 還有就是憑經驗猜然後用數學歸納法證明等等, 對於你的問題最直觀的方法就是畫圖法, 這是一個二叉樹問題, 最開始的序列被遞歸地分為兩份, 因此這棵樹的高度為lg n的下取整(這里我們不討論取整的細節), 層數為1 + lg n, 每一層的合並排序代價總和都為c*n(c為某個常數), 因此整棵樹代價為c*n*lg n + c*n, 因此時間復雜度為O(n*lg n);
也可以用他的表達式求解,這個問題的表達式為:T(n)=2*T(n/2)+O(n)
嚴格來講,上面所說的O更好的替代品為theta(符號打不出來,就用這個代替吧,^_^), 具體可以參考一下機械工業出版社的《演算法導論》
參考資料： 機械工業出版社《演算法導論》

㈢ 各種排序法的時間復雜度到底多少

根據《演算法導論（中文版）》P83表格以及《演算法（中文版）》部分章節內容：

演算法最壞情況運行時間平均情況

冒泡&&插入&&選擇排序 n^2n^2

快速排序n^2 n*log n

希爾排序（希爾增量） n^2 n^(1.3 - 2)

堆排序 n*log n n*log n

註：希爾排序的性能依賴於選擇的增量。

㈣ 遞歸演算法時間復雜度怎麼分析

1、遞歸
是指對一個問題的求解，可以通過同一問題的更簡單的形式的求解來表示. 並通過問題的簡單形式的解求出復雜形式的解. 遞歸是解決一類問題的重要方法. 遞歸程序設計是程序設計中常用的一種方法，它可以解決所有有遞歸屬性的問題，並且是行之有效的. 但對於遞歸程序運行的效率比較低，無論是時間還是空間都比非遞歸程序更費，若在程序中消除遞歸調用，則其運行時間可大為節省. 以下討論遞歸的時間效率分析方法，以及與非遞歸設計的時間效率的比較.
2 時間復雜度的概念及其計算方法
演算法是對特定問題求解步驟的一種描述. 對於演算法的優劣有其評價准則，主要在於評價演算法的時間效率，演算法的時間通過該演算法編寫的程序在計算機中運行的時間來衡量，所花費的時間與演算法的規模n有必然的聯系，當問題的規模越來越大時，演算法所需時間量的上升趨勢就是要考慮的時間度量.
演算法的時間度量是依據演算法中最大語句頻度（指演算法中某條語句重復執行的次數）來估算的，它是問題規模n的某一個函數f(n). 演算法時間度量記作：T（n）=O（f（n））
它表示隨問題規模n的增大，演算法執行時間的增長率和f（n）的增長率相同，稱作演算法的時間復雜度，簡稱時間復雜度[2].
例如下列程序段：
（1）x=x+1;（2）for(i=1;i<=n;i++) x=x+1;（3）for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1. 以上三個程序段中，語句x=x+1的頻度分別為1，n，n2，則這三段程序的時間復雜度分別為O（1），O（n），O（n2）.
求解過程為：先給出問題規模n的函數的表達式，然後給出其時間復雜度T（n）.
但是在現實程序設計過程中，往往遇到的問題都是比較復雜的演算法，就不能很容易地寫出規模n的表達式，也比較難總結其時間復雜度. 遞歸函數就是屬於這種情況. 下面舉例說明遞歸函數的時間復雜度的分析方法.

㈤ 二叉樹排序的演算法時間復雜度問題。依據演算法導論，新建二叉樹的最佳時間復雜度是nlogn，為啥我推的不是

根據Stirling公式：

將分子取對數，並去掉那些常量和低次項不就是得到O(nlog2n)

㈥ 演算法導論裡面的大師解法是什麼 用大師解法計算下面遞歸表達式的時間復雜度. T(n)=2T(n/2) + Θ(n^0.1)

#a i從0循環到n，演算法復雜度為O(n)。
#b 一共要做n^2/2次加法，演算法復雜度為O(n^2)。
#c 要求一個k，滿足2^k>=n ，演算法復雜度為O(log(n))
#d 注意到這個函數做的事跟#c的函數恰好相反，演算法復雜度相同，也是O(log(n))
#e 因為已算出#g每次做3(n-3)次加法，那麼i從1到n，一共做2/3*(n^2-5n+6)次加法，所以復雜度為O(n^2)。
#f 這個函數可以寫成公式T(n)=T(n-2)+T(n-1)，這個遞歸式跟黃金分割有關系，解這個遞歸式，可以知道 T(n) = O((√5-1/2)^n)
#g 函數調用一共做3(n-3)次加法，所以復雜度為O(n)
PenitentSin 這位兄台的#c 算的不對啦，#g也不對。還有#f，這個雖然是遞歸，但不是遞歸就等於指數級的復雜度，要解遞歸方程才能斷定的。
關於演算法復雜度，《演算法導論》一書中第四章有一個主定理，記住這個定理之後，這些問題就小case了（除了復雜遞歸之外）。

㈦ 請問演算法的時間復雜度是怎麼計算出來的

首先假設任意一個簡單運算的時間都是1，例如a=1;a++;a=a*b;這些運算的時間都是1.

那麼例如
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
a++; //注意，這里計算一次的時間是1.
}
那麼上面的這個例子的時間復雜度就是 m*n

再例如冒泡排序的時間復雜度是N*N；快排的時間復雜度是log(n)。

詳細的情況，建議你看《演算法導論》，裡面有一章節，具體講這個的。