背包算法和凸包

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函数的外观进行比较。