書上的演算法平均時間復雜度怎么算？-有解無憂

書上說（因為所有的復雜度，都這么列的，以線性表舉個例子。）
線性表時間復雜度：
最好情況：O(1)
最壞情況：O(n)
平均情況：O(n/2)
然后給出平均時間復雜度為O(n).

我以為的平均時間復雜度就是平均情況下的復雜度了，但是卻是O(n).
這個結果是只考慮最壞情況的時間復雜度得來的，還是另有它法求出來的。
（PS：感覺取個平均時間復雜度的名字真的很容易弄混。）

uj5u.com熱心網友回復：

對時間復雜度而言 n/2 和n 次數都是1 所以可以視作n
就像n+1 和 n-1 都視為n是一個道理
以最高次為準

uj5u.com熱心網友回復：

參考 1 樓 weixin_44521568 的回復:

對時間復雜度而言 n/2 和n 次數都是1 所以可以視作n
就像n+1 和 n-1 都視為n是一個道理
以最高次為準

n是主要增長項

uj5u.com熱心網友回復：

平均就是，(最好+最壞)/2，就好了。

假設N，無窮大。。而且，時間復雜度，只是一個度量的概念。不要求為精確的數字。

那么復雜度為N/2、或N+m(m遠小于N）等等情況。。我們都可以近似的任務，復雜度為N。

所以常見的平均復雜度有
O(N)
O(1)
O(logN)
O(N^2)
等等。

uj5u.com熱心網友回復：

就是算最壞情況呀
普通遍歷陣列：O(n)
哈希表:O(1)
快排：O(logN)
二分:O(log2N)
完全背包動規：O（VP）
還有諸如O(N^2)的復雜度

計算方法：
每次進行一次操作記為O(1）
括號里的未知數為資料最大范圍
例如：遍歷一次長度為N的陣列
時間復雜度為：O(N)

望采納。。

uj5u.com熱心網友回復：

參考 6 樓 Slzde_sub的回復:

你只需要關注最壞時間復雜度就可以了

Quote: 參考 4 樓林多的回復:

平均就是，(最好+最壞)/2，就好了。

假設N，無窮大。。而且，時間復雜度，只是一個度量的概念。不要求為精確的數字。

那么復雜度為N/2、或N+m(m遠小于N）等等情況。。我們都可以近似的任務，復雜度為N。

所以常見的平均復雜度有
O(N)
O(1)
O(logN)
O(N^2)
等等。

誰教你的平均就是相加/2 。。。我佛了

也是個人才？

就算我說的不對。我也是好心回答你呀。。。你也沒必要諷刺我吧。有點禮貌吧。

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/198890.html

標籤：其它技術問題

上一篇：求bp演算法進行iris資料集分類（matlab實作）代碼

下一篇：【C語言】【飛機大戰】游標不移動