線性搜索所用時間的最壞情況是專案位于串列/陣列的末尾，或者不存在。在這種情況下，演算法將需要執行n比較，以查看每個元素是否是所需的值，假設n是陣列/串列的長度。
根據我對 big-O 符號的理解，可以說該演算法的時間復雜度為 O(n)，因為它可能會發生最壞的情況，并且當我們想要時使用 big-O對“最壞情況”進行保守估計。
從 Stack Overflow 上的很多帖子和答案來看，這種想法似乎是有缺陷的，像Big-O 表示法這樣的說法與最壞情況分析無關。
請幫助我以一種不會增加我的困惑的方式來理解這種區別，正如這里的答案：為什么 big-Oh 并不總是演算法的最壞情況分析？做。
我沒有看到大 O 與最壞情況分析無關。從我目前的山頂來看，看起來 big-O 表示最壞情況如何隨著輸入大小的增長而增長，這似乎與最壞情況分析非常“相關”。
諸如此類的宣告，來自https://medium.com/omarelgabrys-blog/the-big-scary-o-notation-ce9352d827ce：
例如，最壞情況分析假設輸入處于最壞可能的狀態，給出最大運算元，而大 o 表示法表示在最壞情況下完成的最大運算元。
沒有多大幫助，因為我看不出所指的是什么區別。
非常感謝任何增加的清晰度。
uj5u.com熱心網友回復：
大 O 符號確實獨立于最壞情況分析。它適用于您想要的任何功能。
在線性搜索的情況下，
最壞情況的復雜度是 O(n)（實際上甚至是 Θ(n)），
平均情況的復雜度是 O(n)（實際上甚至是 Θ(n)），
最佳情況的復雜度是 O(1)（實際上甚至是 Θ(1)）。
因此，大 O 和最壞情況是不同的概念，盡管演算法運行時間的大 O 界限必須適用于最壞情況。
uj5u.com熱心網友回復：
情況是這樣的：
如果找到問題解決方案的演算法在 中
O(f(n))，則意味著該演算法找到問題解決方案的最壞情況是在 中O(f(n))。換句話說，如果g(n)演算法可以分步找到最壞的情況，那么g(n)是O(f(n))。
例如，對于搜索演算法，正如您所提到的，我們知道最壞的情況可以在O(n). 現在，雖然演算法在 中O(n)，但我們可以說演算法O(n^2)也在 中。如您所見，這是Big-Oh復雜性和最壞情況之間的區別。
總之，演算法的最壞情況復雜度是演算法的 Big-Oh 復雜度的一個子集。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313555.html
上一篇：0的單向鏈表頭