为什么求算法的时间复杂度总是取对数的底数为2？
Why is that, the base of the logarithm is always taken as 2 in finding time complexity of algorithms?
考虑这段代码，
function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true
那个内部循环运行 O(n) 次并且每次都做一些工作来计算 n mod i （作为一个非常保守的上限，这当然可以在 O(n^ 3)).因此，整个算法的运行时间为 O(n^4) 并且可能快得多。
我们的算法运行时间为 O(n^4)，但它是输入位数的函数吗？好吧，写出数字 n 需要 O(log n) 位。因此，如果我们让 x 为写出输入 n 所需的位数，则该算法的运行时间实际上是 O(2^(4x))，这不是 x 中的多项式。
我的问题是
To write a number n in bits, it must take log n bits(Base 10). Therefore if we let x be the number of bits, then the actual run time must be O(10^(4x)). This is drastically different from O(2^(4x)). How can we afford to do such an approximation??
除非你使用任意大的数字（因此 bignum 库），整数适合寄存器并直接由 CPU 指令详细说明，这些指令需要恒定的时间来执行 1 无论输入中有多少 "on" 位。因此，内部循环中的 modulo 操作是 O(1).
另一方面，如果n真的没有边界，当然我们不能再说mod是O(1)了。
现在，即使我们想象该算法在数字的位数方面是多项式的，您选择什么基数并不重要：假设 mod 是 O(d^a) 其中d 是 n 的小数位数（即 d=log10(n) ）；不同底数的对数仅因乘法因子不同，所以我们有 log10(n) = k log2(n)，因此 O((log10(n))^a) = O(k^a (log2(n))^ a) = O((log2(n))^a) 因为大 O 表示法对乘法常数不感兴趣，所以你看其实是一样的。
- 这在简单的 CPUs 上是完全正确的，对于每条指令，您可以准确地说出机器周期数； modern CPUs 更复杂，单个指令的成本更难确定，但它通常不依赖于输入的确切位模式。
对数底数之间的换算相当于乘以某个常数。常量乘法不影响大O复杂度class。所以对数底对分析没有影响
但是，您问题中的示例并不是关于对数的。这有点相反，因为它是关于指数表达式的。但我并不完全理解这个例子，因为短语“它必须采用 log n 位（基数 10）”对我来说没有意义。正如您断言的那样，数字 n 实际上有大约 log n (base 2) 位，而不是以 10 为基数。
您的函数要么接受 n 的 base-2 表示，要么接受 base-10 表示，而不是两者。在第一种情况下，输入大小明确为 x = log_2(n)，而在后一种情况下，输入大小无疑为 x = log_10(n)。如果您的算法花费的时间与 n^4 成正比（例如），那么第一台机器执行 O((2^x)^4 = O(2^(4x))，而在后者中花费 O((10^x)^4) = O(10^(4x))。事实上，10^(4x) 渐近增长比 2^(4x) 快得多，这很容易验证。
这通常不被视为问题，因为假定机器模型对于给定分析保持不变。很容易证明改变机器模型可以改变很多关于复杂性的事情；例如，已知检测回文在 RAM 机器中需要线性时间，在单带确定性图灵机中需要二次时间。
更重要的是给定模型的一致性。而且，只要您保持在给定模型（机器是二进制或十进制）内，就没有后顾之忧。
"But wait"，你说，"I can be on one machine and pass in strings encoding my input as either binary or decimal!"这个是真的。然而，在这种情况下，与采用 O(n) 的十进制算法相比，采用 base-2 表示并需要 O(n) 的算法实际上更快（作为输入的函数）。为什么？因为 n 在每种情况下都是输入大小的指数函数，而 2 是比 10 小的基数。所以在这种情况下它确实告诉了我们有用的信息（但请注意，我们在这里没有取任何对数，只是做了指数）。
实际上，您将对数与指数混为一谈，因为两者都涉及分析函数的运行时间。对数的底数可以互换，但指数的底数不能。
考虑这段代码，
function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true
那个内部循环运行 O(n) 次并且每次都做一些工作来计算 n mod i （作为一个非常保守的上限，这当然可以在 O(n^ 3)).因此，整个算法的运行时间为 O(n^4) 并且可能快得多。
我们的算法运行时间为 O(n^4)，但它是输入位数的函数吗？好吧，写出数字 n 需要 O(log n) 位。因此，如果我们让 x 为写出输入 n 所需的位数，则该算法的运行时间实际上是 O(2^(4x))，这不是 x 中的多项式。
我的问题是
To write a number n in bits, it must take log n bits(Base 10). Therefore if we let x be the number of bits, then the actual run time must be O(10^(4x)). This is drastically different from O(2^(4x)). How can we afford to do such an approximation??
除非你使用任意大的数字（因此 bignum 库），整数适合寄存器并直接由 CPU 指令详细说明，这些指令需要恒定的时间来执行 1 无论输入中有多少 "on" 位。因此，内部循环中的 modulo 操作是 O(1).
另一方面，如果n真的没有边界，当然我们不能再说mod是O(1)了。
现在，即使我们想象该算法在数字的位数方面是多项式的，您选择什么基数并不重要：假设 mod 是 O(d^a) 其中d 是 n 的小数位数（即 d=log10(n) ）；不同底数的对数仅因乘法因子不同，所以我们有 log10(n) = k log2(n)，因此 O((log10(n))^a) = O(k^a (log2(n))^ a) = O((log2(n))^a) 因为大 O 表示法对乘法常数不感兴趣，所以你看其实是一样的。
- 这在简单的 CPUs 上是完全正确的，对于每条指令，您可以准确地说出机器周期数； modern CPUs 更复杂，单个指令的成本更难确定，但它通常不依赖于输入的确切位模式。
对数底数之间的换算相当于乘以某个常数。常量乘法不影响大O复杂度class。所以对数底对分析没有影响
但是，您问题中的示例并不是关于对数的。这有点相反，因为它是关于指数表达式的。但我并不完全理解这个例子，因为短语“它必须采用 log n 位（基数 10）”对我来说没有意义。正如您断言的那样，数字 n 实际上有大约 log n (base 2) 位，而不是以 10 为基数。
您的函数要么接受 n 的 base-2 表示，要么接受 base-10 表示，而不是两者。在第一种情况下，输入大小明确为 x = log_2(n)，而在后一种情况下，输入大小无疑为 x = log_10(n)。如果您的算法花费的时间与 n^4 成正比（例如），那么第一台机器执行 O((2^x)^4 = O(2^(4x))，而在后者中花费 O((10^x)^4) = O(10^(4x))。事实上，10^(4x) 渐近增长比 2^(4x) 快得多，这很容易验证。
这通常不被视为问题，因为假定机器模型对于给定分析保持不变。很容易证明改变机器模型可以改变很多关于复杂性的事情；例如，已知检测回文在 RAM 机器中需要线性时间，在单带确定性图灵机中需要二次时间。
更重要的是给定模型的一致性。而且，只要您保持在给定模型（机器是二进制或十进制）内，就没有后顾之忧。
"But wait"，你说，"I can be on one machine and pass in strings encoding my input as either binary or decimal!"这个是真的。然而，在这种情况下，与采用 O(n) 的十进制算法相比，采用 base-2 表示并需要 O(n) 的算法实际上更快（作为输入的函数）。为什么？因为 n 在每种情况下都是输入大小的指数函数，而 2 是比 10 小的基数。所以在这种情况下它确实告诉了我们有用的信息（但请注意，我们在这里没有取任何对数，只是做了指数）。
实际上，您将对数与指数混为一谈，因为两者都涉及分析函数的运行时间。对数的底数可以互换，但指数的底数不能。