驗證算法的上限和下限

如何驗證算法的上限和下限？驗證算法的上限和下限

到目前爲止，我認爲算法的上下界都需要考慮所有的輸入並顯示它不會比f（n）[上限]做得更差，而不是優於g（n）[下限]。

我的講師表示，對於上限，人們需要證明它一般[考慮所有輸入]，但對於下限來說，一個例子就足夠了。

這真讓我困惑。任何人都可以澄清他的意思嗎？

2015-04-20 XerXes

你的講師是錯的 - 或者你誤解了他。如果你想表現出g（n）的最佳表現 - 你需要：（1）證明沒有輸入比g（n）好。（2）（如果你想要它是嚴格的）顯示一些性能與g（n）相同的輸入，與上限（但在另一個方向）相同。 – amit

如果您講師講最壞的行爲，您的講師是對的。

從一個例子中，你可以說運行時間「至少是那麼多」（並且可能更糟糕），但並不是說它「至多有那麼多」（因爲它可能更糟）。

[對稱，最好的情況行爲的說話時，一個單一的情況下，給出的上界的保證。]

的下限和上限是完全不同的事情。下限通常是「普遍」建立的，即不考慮任何特定的算法。例如，在最壞的情況下，您不能對小於N.Log（N）的比較排序，因爲您需要區分N！可能的排列，並且需要收集Lg（N！）比特的信息。

相反，對於特定算法確定上界。例如，HeapSort永遠不會超過2N.Lg（N）的比較。當上限滿足下限時，算法被認爲是有效的。

2015-04-20 07:49:36

不，他不是。以快速排序爲例（以pivot作爲第一個元素），並給出了排序數組的示例。是「下限」（最佳表現）Theta（n^2）？ – amit

是的，歐米茄（N²）是最壞情況下的下限。 –

我不認爲他的意思是什麼，我相信他算法的「上限」和「下限」實際上意味着（措辭不佳）最好和最壞情況的表現，而不是最差情況下的O和Omega。 – amit

回答