algorithm - 如何以大 O 表示法计算 O(log n)？

Question

我知道这O(log n)指的是通过问题集的固定比率（以大 O 表示法）的迭代减少，但我如何实际计算它以查看具有复杂性的算法必须对它之前的问题集N执行多少次迭代完成（还剩一个元素）？log NN

score 3 · Accepted Answer

你不能。您无需使用 BigO 计算确切的迭代次数。

当您有精确的迭代次数公式时，您可以“推导出”BigO。

BigO 只是提供信息迭代次数如何随着 N 的增长而增长，并且仅适用于“大”N。

不多也不少。有了这个，您可以得出结论，如果您有一些样本运行，算法将花费多少操作/时间。

score 1 · Accepted Answer

用 Tim Roughgarden 在他的算法课程中的话表达：

big-Oh 符号试图为高级算法推理提供一个甜蜜点

这意味着它旨在描述算法时间执行与其输入大小之间的关系，避免依赖于系统架构、编程语言或选择的编译器。

想象一下 big-Oh 表示法可以提供准确的执行时间，这意味着对于任何知道其 big-Oh 时间复杂度函数的算法，您都可以预测它在任何机器上的行为。

另一方面，它以渐近行为为中心。也就是说，它的描述对于大n值更准确（这就是为什么在 big-Oh 表示法中忽略算法时间函数的低阶项）。可以推断，低值n并不要求您努力提高算法性能。

score 0 · Accepted Answer

大 O 表示法仅显示一个数量级 - 而不是算法将执行的实际操作数。如果您需要计算循环迭代或基本操作的确切次数，则必须手动完成。然而，在大多数实际用途中，确切的数字是无关紧要的 -O(log n)告诉你 num. 的操作将以对数方式增加n

score 0 · Accepted Answer

从大 O 表示法中，您无法准确判断算法将进行多少次迭代，这只是估计。这意味着对于较小的数字，log(n) 和实际迭代次数之间的差异可能会有显着差异，但越接近无穷大，差异就越不显着。

score 0 · Accepted Answer

如果您做出一些假设，您可以将时间估计为一个常数因子。最大的假设是，当大小趋于无穷大时，限制行为与您关心的问题大小的实际行为相同。

N在这种假设下，大小问题的时间上限是C*log(N)某个常数C。该常数将根据您用于计算对数的底数而变化。只要您对此保持一致，基础就无关紧要。如果您有一种尺寸的测量时间，您可以估计C并使用它来猜测不同尺寸的时间。

例如，假设大小为 100 的问题需要 20 秒。使用常用对数，C是 10。（100 的常用对数是 2）。这表明大小为 1000 的问题可能需要大约 30 秒，因为 1000 的常见日志是 3。

然而，这是非常粗糙的。该方法对于估计算法是否可用于解决大问题最有用。在这种情况下，您还必须注意内存大小。一般来说，设置一个问题的规模至少是线性的，因此它的成本会比O(log N)操作增长得更快。

5 回答 5