平均情況與攤銷分析之間的區別

我正在閱讀關於算法分期分析的文章。以下是一段文字摘錄。平均情況與攤銷分析之間的區別

攤銷分析類似於平均情況分析，因爲它是涉及一系列操作的平均成本。然而，平均案例分析依賴於關於數據結構和操作的概率假設以便計算算法的預期運行時間。因此其適用性取決於關於算法輸入的概率分佈的某些假設。

的平均約束的情況下不排除一個將得到「不吉利」，並遇到需要更多超預期時間即使輸入概率分佈的假設有效的輸入的可能性。

我對上面的文字片斷的問題是：

在第一段中，如何平均情況分析「依靠關於數據結構和操作的概率假設？」我知道平均情況分析取決於輸入的可能性，但是上面的表述意味着什麼？
作者在第二段中的含義是什麼？即使輸入分佈是有效的，平均情況也是無效的？

謝謝！

來源

2011-09-07 venkysmarty

檢查了這一點，第二個評論，非常非常好！哈哈 http://programmers.stackexchange.com/questions/161404/amortized-analysis-worst-case-performance-guarantees –

@sorry_I_wont看起來像評論已被刪除，因爲我沒有看到任何。 –

爲了得到平均情況時間複雜度，你需要做什麼「平均情況」是假設。如果輸入是字符串，什麼是「平均字符串」？只有長度重要嗎？如果是這樣，我會得到的字符串的平均長度是多少？如果不是，這些字符串中的平均字符數是多少？例如，如果字符串是姓氏，則很難回答這些問題。平均姓氏是多少？
在最有趣的統計樣本中，最大值大於平均值。這意味着您的平均案例分析有時會低估某些投入所需的時間/資源（這是有問題的）。如果你仔細想想，對於一個對稱的PDF，平均情況分析應該低估它高估的程度。最差的案例分析，OTOH，只考慮最有問題的案例，因此保證高估。

來源

2011-09-07 13:09:21 Patrick87

考慮計算未排序數組中的最小值。也許你知道它有O(n)運行時間，但如果我們想要更精確，它在平均情況下會比較n/2。爲什麼這個？因爲我們正在對數據做一個假設;我們假設最小值可以以相同的概率存在於每個位置。如果我們改變這個假設，並且我們說例如在i位置的概率是隨着i增加的，我們可以證明一個不同的比較數字，甚至是不同的漸近界限。
在第二段中，作者說，對於平均案例分析，我們可能非常不走運，並且測量的平均案例大於合理案例;回想一下前面的例子，如果我們在m個不同的大小爲n的數組上運行不幸，並且最小值是每次都在最後一個位置，那麼我們將測量一個n平均值事例，而不是n/2。這種情況不可能發生在攤銷邊界被證實時。

來源

2011-09-07 13:00:42 Simone

如何計算只有n/2比較的未排序數組中的最小值？我認爲你需要完全n-1。而不僅僅是平均而且總是。 –

平均案例分析對在某些情況下可能無法滿足的輸入進行假設。因此，如果您的輸入不是隨機的，則在最壞的情況下，算法的實際性能可能比平均情況慢得多。

攤銷分析不會做出這樣的假設，但它會考慮一系列操作的總體性能，而不僅僅是一項操作。

動態數組插入提供了一個簡單的攤銷分析示例。一種算法是分配一個固定大小的數組，並在插入新元素時，在必要時分配一個固定大小的數組，其長度加倍。在最壞的情況下，插入可能需要與整個列表的長度成正比的時間，所以在最壞的情況下插入是O（n）操作。但是，您可以保證這種最糟糕的情況很少發生，因此插入是使用攤銷分析的O（1）操作。無論投入是什麼，攤銷分析都是一樣的。

來源

2011-09-07 13:56:49 RossFabricant

平均情況與攤銷分析之間的區別

回答

相關問題