揹包算法和凸包

Question

我正在採取算法分析課程，我在java中有算法作業。我編寫了這個程序，效果很好。然而，我的老師想要報告與最壞情況下的加分結果相比較的情況。這是什麼意思？我如何比較？第一個是凸包算法，第二個是揹包算法。我的凸包的複雜性n^3有最壞的情況。他爲什麼想要最壞的情況？我的揹包算法複雜度是（n * 2^n）。你可以幫我嗎？

Answer 1

要求您比較算法的漸近複雜性並用一些數據證明它。這應該給你一些關於複雜性與實際運行時間之間的聯繫的概述。

他們要求最壞的情況，因爲通常情況下，這是您可以爲您提供的解決方案提供的保證。例如，如果算法在第一次嘗試時絆倒了解決方案，那麼揹包可能立即運行n = 1000，但不能保證它適用於任何大小的輸入（時間過長）。

現在，您已經具有複雜性，所以O（n^3）< O（n2^n），因此當您比較複雜性時，船體會更快。現在以n = 1,2,3,4,5,10,20,25,30,50,100,500,1000爲例，並給出解決方案。您可能會發現，對於n的小值，時序大致相同，並且它們不按照複雜性行事，但隨着n（n^3）增長在合理的時間內完成，而O（n2^n）將花費太長時間（幾分鐘後停止）。繪製您的結果並與x^3和x2^x函數的外觀進行比較。