algorithm - 算法复杂性：决定对数基数的因素

Question

在对数复杂性的情况下，决定对数底的因素是什么？我已经阅读了关于 SO 的相关问题（像这样）。在二进制搜索、二叉树遍历等情况下，日志的基数为 2，因为每次将数据分成两份。但我仍然无法理解/想到其他基地的例子。其他对数复杂度基的例子是什么？

score 2 · Accepted Answer

从一个碱基到另一个碱基的变化涉及乘以一个常数，这不会改变复杂性，因此碱基的选择并不重要。O(log(N)) = O(log(N))。

例如，如果某个算法涉及在大 N 的极限中接近 K = 1.23 log ₂ (N) 的多个步骤，其中 N 是问题的某个参数，那么极限也可以写为 K = 3.45 log ₇ (N)。

指数的复杂性是我以前从未听说过的。我认为它完全有意义的唯一方法是这样的：Z = B ^O(log(N))意味着存在一个常数 M 使得对于所有足够大的 N， Z ≤ B ^{M ln(N)}。

score 0 · Accepted Answer

当你解决一个大问题时，通常你把它分成更小的部分，即所谓的分而治之，例如在快速排序算法中，在每个阶段，数组的大小减半，直到大小足够小并且有解决方案变得微不足道。这里的因子是 2，因为在每个阶段问题的大小都除以 2。这是另一个例子：

将十进制数转换为字符串

while (n > 0) {
    digits.add(n % 10);
    n /= 10;
}
print digits.reverse();

I 每次迭代n减少到十分之一。所以算法的复杂度是 O(log_10 n) 。例如，如果 n = 1,000,000,000，则算法最多将在 9 步 = log_10 (1,000,000,000) 后终止。如果n在基数k中，则将while10 替换为k，复杂度变为 O(log_k n)。

2 回答 2