algorithm - 在运行时间算法中如何计算类似效率的 N 值？

Question

我试图理解运行时间的计算，但是，我陷入了僵局。如果你有两个功能，比如

    (N^3 + 2N^2 + 6N + 3)

和

    (6N^2 + 4N + 10)

您如何找到使两种算法达到相同效率的 N 值？我宁愿不给出实际值，而是给出如何解决问题。我为 N^3 和 6N^2 插入了 0、1、4、10 和 67(给定的选择)，但在每种情况下 N^3 总是较小(当然 0 除外)。我做错了吗？

Answer 1

是的，你做错了。更准确地说，您尝试做的是不正确的，至少作为大 O 表示法的使用是这样。

首先，大 O 符号会丢弃多项式的最高阶部分以外的所有内容，因此您的两个示例正确地为 O(N³) 和 O(N²) 分别。 Big-O 表示法与 N 接近无穷大时的行为相关。

基于此，我们很快就会发现大 O 表示法(通常)根本不是用于您尝试完成的工作的正确工具。现在，也许你对 O 的使用真的是这里的错误，你的意思是在第一种情况下，时间与 N³ + 2N^{2< 成正比/sup>+6N+3，在第二种情况下为 6N2+4N+10。}

如果是这样，那么你只需要求解两个多项式相等的点:

N³ + 2N²+6N+3 = 6N²+4N+10

...然后我们将其转换为:

N³ - 4N² + 2N - 7 = 0

从那里开始，这是一个简单的代数问题来解决 N。

N (N² - 4N + 2) = 7

在这种情况下，我倾向于假设低阶项变得越来越近似，所以(例如)当你得到常数项时(即不涉及 N)它确实很近似。因此，在求解 N 时，我可能不会太担心让这些项精确正确。基于此，我们可以将上面的等式转换为:

N (N-2)(N-2) = 7

然后我再作弊，观察到我们有 N-2 作为两个因素，N 作为第三个因素，所以 N 是 7 + 2 的立方根附近的某处，结果大约为 4。由于其中一个因素实际上是 N，而不是 N-2，我们知道这不是完全，但实际上 N 只能是整数，所以它可能足够接近.如果你想检查这一点，你可以将 3、4 和 5 插入到原始多项式中，然后计算这些值。我的猜测是，对于 3，你会在一个方向上得到差异，对于 5，在另一个方向上，而对于 4，差异小于 3 或 5。

不过，四只是这些多项式数学的粗略近似值。在现实生活中可能不会这样。考虑到多项式次数的不同，真正的盈亏平衡点与此有所不同也就不足为奇了——很可能是 3 或 5，甚至很可能是 2 或 6。我，举个例子, 如果它大到 100 甚至可能是 50，那真的会很惊讶。这就是为什么我不太担心在原始计算中特别精确的原因。

我可能应该补充一点，在大多数实际情况下，您也不会以几乎与“N³ + 2N²+ 6N + 3”一样精确的任何东西开始。实际上，您经常在测量中开始时有足够多的噪声，以至于很难确定多项式的最重要项是什么。例如，考虑一下我在 previous answer 中展示的一些真实数据关于快速排序所花费的时间。这是一个多年来被大量研究(和测试)的算法，所以几乎没有真正的问题是它的预期运行时间大约是 N log N。尽管如此，基于我用来在那篇文章中绘制图表的原始时间，很难确定它确实是 N log N 而不仅仅是线性的。

因此，我要警告说，根据我的估计，这个问题的基础是相当值得怀疑的(即使充其量)，除非是纯粹的智力练习。