1樓：匿名使用者
一般來說, 標準的分治法合併排序時間複雜度為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(符號打不出來,就用這個代替吧,^_^), 具體可以參考一下機械工業出版社的《演算法導論》
2樓：匿名使用者
o(nlgn)
對於時間複雜度，最容易理解的就是把它看做一顆樹，每個根節點有兩個兒子，做兒子代表(being, mid), 有兒子代表(mid, start)
最後形成一顆2叉樹
深度為lgn，即為其複雜度，再乘以線性的o(n)總複雜度nlgn
沒有圖，不太好說。你的書上後面章節肯定有2叉樹，就是那個形式，可以先看一下，只看形式就可以，就很好理解了。
時間複雜度問題
3樓：匿名使用者
n就是問題的規模，因此a答案不對，答案是c，時間複雜度就是執行時間，o代表同數量級，至於答案b，則是c中包含的特例，一般o(n^2)得演算法並不一定是執行時間等於n^2
程式設計中時間複雜度問題
4樓：匿名使用者
引用：「一個程式的時間複雜度是:o(n),其執行時間為:1000ms另一個程式的時間複雜度是:o(n^2),其執行時間大概是多少?」
一般不能如此推算的：如果硬是要這麼做：結果可以是1000^2 (因為n^2是n的平方，這是不對的)
同為o(n)時間複雜度的演算法，係數也是不一樣的 時間也不等更不能由此推算出另一個程式的時間複雜度的大概執行時間。
一般只能從問題的資料規模以及多種測試資料的平均情況下粗略比較不能如此比較的
而且同一測試資料，還要看是什麼資料，有時候，同一特殊測試資料o(n^2)的可能並不比o(n)慢多少
只能具體執行得出結果。
你的問法，沒多大意義
5樓：匿名使用者
要知道它的偏移量,比如你這裡的m[a][b]就直接找到了,所以就是o(1)常量
再舉個例子做比較,比如磁帶(錄音機的那種) 如果你找到第3個位子的內容,一定要先經過1,2,3.找第4個位子的,就要經過1,2,3,4這樣的情況,時間複雜度就是線性遞增的了,因此時間複雜度為o(n)
6樓：
時間複雜度的單位不是任何時間單位哦，注意看時間複雜度的定義。
1ghz 的cpu就是每秒 十億次 運算，就是說第一個程式大約要執行十億條彙編指令。由此可知第二個程式最壞情況下要執行十億的2次方條彙編指令，1ghz的cpu要耗時十億秒。
當然這個比喻不是很精確，畢竟現在的作業系統都是搶佔式，1ghz的cpu輪到某個程式一秒大概也就算幾百萬次。
如何分析時間複雜度 線性表
演算法分析。同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間複雜度和空間複雜度來考慮。1 時間複雜度。1 時間頻度。一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機執行測試才能知道。...
求問個c語言問題 這個演算法的時間複雜度怎麼看
時間複雜度等於內層迴圈的值，不算外層的。內層是x那麼時間複雜度記為o 1000 如果是並列的，比如。x 0 y 0 while x 100 x while y 100 y 這個並列的就記為o 100 100 o 200 看它的迴圈語句，while語句會執行1000次。c語言演算法的時間複雜度如何計算...
資料結構“時間複雜度”的題目，資料結構 有關時間複雜度題目 求高手！求詳細解釋
麗江旅遊指南網 o表示法首先要弄清楚什麼用它來代表的上限的漸近執行時間的演算法函式g n o g n 代表了一組函式。介紹到演算法書定義 o g n 看到上面也可以忽略不明白，你只需要知道在低階項的漸近積極的作用，在確定上限和下限，可以忽略不計，因為當n大，他們相對來說並不重要，指數最高的專案上腳的...