1樓：匿名使用者
時間複雜度
演算法分析
同一問題可用不同演算法解決，而乙個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。乙個演算法的評價主要從時間複雜度和空間複雜度來考慮。
1、時間複雜度
（1）時間頻度
乙個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機執行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且乙個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。
乙個演算法中的語句執行次數稱為語句頻度或時間頻度。記為t(n)。
（2）時間複雜度
在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度t(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間複雜度概念。
一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函式，用t(n)表示，若有某個輔助函式f(n),使得當n趨近於無窮大時，t（n)/f(n)的極限值為不等於零的常數，則稱f(n)是t(n)的同數量級函式。記作t(n)=o(f(n)),稱o(f(n)) 為演算法的漸進時間複雜度，簡稱時間複雜度。
在各種不同演算法中，若演算法中語句執行次數為乙個常數，則時間複雜度為o(1),另外，在時間頻度不相同時，時間複雜度有可能相同，如t(n)=n2+3n+4與t(n)=4n2+2n+1它們的頻度不同，但時間複雜度相同，都為o(n2)。
按數量級遞增排列，常見的時間複雜度有：
常數階o(1),對數階o(log2n),線性階o(n),
線性對數階o(nlog2n),平方階o(n2)，立方階o(n3),...，
k次方階o(nk),指數階o(2n)。隨著問題規模n的不斷增大，上述時間複雜度不斷增大，演算法的執行效率越低。
時間複雜度 t(n)=o(f(n)),的 o什麼意思
2樓：1麼麼麼麼麼噠
o(n)這個大o表示的是最壞情況下的時間複雜度，就比如你舉的例子，一共n^3次乘法和n^3次加法，那麼加起來就是2×n^3。然後如果有乙個表示式f(n)，使得n趨於無窮大的時候，lim(2×n^3)/f(n)=常數c，那麼就可以用大o表示。表示為o(f(n))，而且規定f(n)的表示式是不帶常數的係數的，那麼在這裡f(n)=n^3。
一般用大o表示演算法複雜度只需要取次數最高的項，而且去掉係數就ok了，不用每次都這麼算的。三重迴圈而且每重迴圈都執行n次的話直接o(n^3)就好了。
c語言，時間複雜度與空間複雜度，演算法時間公式t(n)=o(f(n))，與空間公式s(n)=o（f（n））
3樓：匿名使用者
演算法的時間複雜度：
為了便於比較同一問題的不同演算法，通常從演算法中抽取一種或者多種有代表性的基本操作，再以這些基本操作重複執行的次數與問題規模的關係t(n) 作為演算法的時間性量度。
如果t(n) 和 f(n) 是n 的函式，當n →∞ 時，有t(n) / f(n) → c (常數c ≠ 0)，記作：t(n) = o(f(n))，稱o(f(n)) 為演算法的漸近時間複雜度，簡稱時間複雜度。
演算法的空間複雜度：
乙個演算法實現所佔儲存空間大致包含三方面：
1. 指令、常數、變數所佔用的儲存空間；
2. 輸入資料所佔用的儲存空間；
3. 演算法執行時所需的輔助空間；
前兩者是必須的，通常將演算法執行時所需的輔助空間作為分析演算法空間複雜度的依據：s(n) = o(f(n))，其中f(n)的規則與時間複雜度一致。
如果乙個演算法的時間複雜度是o(f(n)).試解釋o(f(n))的含義 並畫圖描述
4樓：心の在り処
設演算法執行時間為 g(n)
g(n) = o(f(n)) 表明 存在n，及常數c， 當 n > n 時 g(n) <= c*f(n)
對於演算法的時間複雜度為f（n）這個問題的規模是什麼意思
5樓：種花家的小公尺兔
演算法的時間複雜度不僅僅依賴於問題的規模，還與輸入例項的初始狀態有關。演算法中的指令描述的是乙個計算，當其執行時能從乙個初始狀態和（可能為空的）初始輸入開始。
經過一系列有限而清晰定義的狀態，最終產生輸出並停止於乙個終態。乙個狀態到另乙個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。
程式呼叫自身的程式設計技巧稱為遞迴（recursion）。乙個過程或函式在其定義或說明中有直接或間接呼叫自身的一種方法，它通常把乙個大型複雜的問題層層轉化為乙個與原問題相似的規模較小的問題來求解，遞迴策略只需少量的程式就可描述出解題過程所需要的多次重複計算，大大地減少了程式的**量。
遞迴的能力在於用有限的語句來定義物件的無限集合。一般來說，遞迴需要有邊界條件、遞迴前進段和遞迴返回段。當邊界條件不滿足時，遞迴前進；當邊界條件滿足時，遞迴返回。
6樓：匿名使用者
從數學上定義，給定演算法a，如果存在函式f(n)，當n=k時，f(k)表示演算法a在輸入規模為k的情況下的執行時間，則稱f(n)為演算法a的時間複雜度。
這裡首先要明確輸入規模的概念。關於輸入規模，不是很好下定義，非嚴格的講，輸入規模是指演算法a所接受輸入的自然獨立體的大小。例如，對於排序演算法來說，輸入規模一般就是待排序元素的個數，而對於求兩個同型方陣乘積的演算法，輸入規模可以看作是單個方陣的維數。
為了簡單起見，總是假設演算法的輸入規模是用大於零的整數表示的，即n=1,2,3,……,k,……
對於同乙個演算法，每次執行的時間不僅取決於輸入規模，還取決於輸入的特性和具體的硬體環境在某次執行時的狀態。所以想要得到乙個統一精確的f(n)是不可能的。為了解決這個問題，做以下兩個說明：
1.忽略硬體及環境因素，假設每次執行時硬體條件和環境條件是完全一致的。
2.對於輸入特性的差異，將從數學上進行精確分析並帶入函式解析式。
7樓：匿名使用者
問題規模：就是指你演算法中所涉及的區域性來看資料量大的大小。如：
求100以內還是1000以內的素數。演算法的執行速度，表現為演算法的時間複雜度。其中時間複雜度還與演算法的選用策略、書寫程式的語言、編譯所產生的機器**質量、機器指令執行速度有關。
如： for(i=1;i<=n;++i) for(j=1;j<=n;++j)t(n)=o(n^3);一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函式f（n）,t(n)=o(f(n))稱為漸進時間複雜度，也稱時間複雜度。
8樓：fly杜少
我的回答有問題，編輯掉了
計算機演算法是問題規模n的函式f(n)，演算法的時間複雜度也因此記做:t(n)=o(f(n))
9樓：匿名使用者
還少了一點，是n趨於無窮大時的無窮大階次
演算法時間複雜度的表示法o(n²)、o(n)、o(1)、o(nlogn)等是什麼意思？
10樓：匿名使用者
o(n²)表示關於n的2階無窮小量。當n線性增長時，計算量按n²規律增大。
o(1)表示計算量不變。
其它類似
11樓：匿名使用者
演算法的時間複雜度是乙個函式，它定量描述了該演算法的執行時間。這是乙個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述,隨著模組n的增大，演算法執行的時間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小，演算法的時間複雜度越低，演算法的效率越高.
例：演算法：
for(i=1; i<=n; ++i)
}則有 t(n) = n 的平方+n的三次方，根據上面括號裡的同數量級，我們可以確定 n的三次方 為t（n）的同數量級
則有 f(n) = n的三次方，然後根據 t(n)/f(n) 求極限可得到常數c
則該演算法的時間複雜度：t(n) = o(n^3)
乙個演算法的時間複雜度是什麼函式？
12樓：匿名使用者
時間複雜度是度量演算法執行的時間長短，演算法的時間複雜度記做：t（n）=o（專f（n））
分析：隨著模組n的增大，屬演算法執行的時間的增長率和f（n）的增長率成正比，所以f（n）越小，演算法的時間複雜度越低，演算法的效率越高。
在計算時間複雜度的時候，先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出t（n）的同數量級（它的同數量級有以下：1，log2n ，n ，nlog2n ，n的平方，n的三次方，2的n次方，n！），找出後，f（n）=該數量級，若t(n)/f(n)求極限可得到一常數c，則時間複雜度t（n）=o（f（n））
13樓：匿名使用者
關於n的函式，n是問題的規模
跪求《演算法設計與分析》的課後習題答案，編者王紅梅，清華大學出
樓上的諸位兄弟們，給小弟也來點湯。495965292 樓主，跪求發乙份來給我吧，772344824 謝謝了 能發我乙份嗎？980491262 萬分感謝 給我也發乙份1075540012 求 演算法設計與分析 王紅梅版的課後答案和實驗 你好，樓主。很高興看到你的問題。但是又很遺憾到現在還沒有人回答你的...
誰能給我一本好的《演算法設計與分析》教材，給初學者用，謝謝啦
1.資料結構與演算法分bai 析 c語言描述 原書du 第2版 美 維斯zhi 機械工業出dao版版社 2.演算法導論 原書第2版 美 科曼權 cormen,t.h.機械工業出版社第一本可作教材，391頁 不厚 經典,翻譯不錯。第二本可作參考書，754頁,演算法地位高，經典。涉及 演算法 的東西就不...
在下列排序演算法中，哪演算法的時間複雜度與初始排序無關
d不管原陣列是什麼樣子，每一次你都要遍歷一邊剩餘的數來選取最大 最小值 演算法的時間複雜度與初始排序無關的都有什麼排序 常見的幾種排序演算法複雜度如下 方式 平均 最壞 最好 插入 n 回2 n 2 n 希爾 n 1.3 冒泡 n 2 n 2 n 快速 nlogn n 2 nlogn 選擇 n 2 ...