我最近了解了算法的正式 Big-O 分析；但是，我不明白为什么这两种几乎做同样事情的算法会有截然不同的运行时间。这两种算法都打印数字 0 到 n。我将用伪代码编写它们:
Algorithm 1:
def countUp(int n){
for(int i = 0; i <= n; i++){
print(n);
}
}
Algorithm 2:
def countUp2(int n){
for(int i = 0; i < 10; i++){
for(int j = 0; j < 10; j++){
... (continued so that this can print out all values 0 - Integer.MAX_VALUE)
for(int z = 0; z < 10; z++){
print("" + i + j + ... + k);
if(("" + i + j + k).stringToInt() == n){
quit();
}
}
}
}
}
因此，第一个算法的运行时间为 O(n)，而第二个算法(取决于编程语言)的运行时间接近于 O(n^10)。代码中是否存在任何导致这种情况发生的原因，或者仅仅是我的示例的荒谬性“破坏”了数学？
最佳答案
在 countUp 中，循环命中 [0,n] 范围内的所有数字一次，因此导致运行时间为 O(n)。
在 countUp2 中，您会做很多次完全相同的事情。所有循环的界限都是 10。
假设您有 3 个循环，边界为 10。因此，外循环执行 10，内循环执行 10x10，最内循环执行 10x10x10 .因此，最坏的情况是您的最内层循环将运行 1000 次，这基本上是常数时间。因此，对于边界为 [0, 10) 的 n 循环，您的运行时间为 10^n，这又可以称为常数时间 O(1)，因为它不依赖于 n 最坏情况分析。
假设您可以编写足够多的循环并且 n 的大小不是一个因素，那么您将需要一个循环来处理 n 的每个数字。 n 中的位数是 int(math.floor(math.log10(n))) + 1；让我们称之为 dig。因此，迭代次数的更严格上限是 10^dig(可以减少到 O(n)；证明留给读者作为练习)。
关于algorithm - 基本 "Algorithm"的 Big-O 分析不一致，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36752654/