java - 背包算法和凸包

Question

我正在上算法分析类(class)，我有 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 的增长，O(n^3) 在某个合理的时间内完成，而 O(n2^n)将花费太长时间(几分钟后停止)。绘制您的结果并将其与 x^3 和 x2^x 函数的外观进行比较。