基本 "Algorithm" 的 Big-O 分析中的不一致
Inconsistencies in Big-O Analysis of a Basic "Algorithm"
我最近了解了算法的正式 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)。代码中是否有任何导致这种情况发生的原因，或者仅仅是我的示例的荒谬性 "breaks" 数学？
在 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)；证明留给 reader 作为练习）。
在分析算法的 运行 时间时，要寻找的一个关键因素是循环。在算法 1 中，您有执行 n 次的代码，使得 运行time O(n)。在算法 2 中，您有每个 运行 10 次的嵌套循环，因此您的 运行 时间为 O(10^3)。这是因为对于中间循环的每个 运行，您的代码 运行s 最内层循环 10 次，而最外层循环的每个 运行 又 运行s 10 次.所以代码运行s 10x10x10次。 （然而，这纯粹是一个上限，因为您的 if 语句可能会在循环完成之前结束算法，具体取决于 n 的值）。
要在countUp2中计数到n，则需要与n中的位数相同的循环次数：因此log(n)次循环。每个循环可以运行10次，所以总的迭代次数是10^log(n)也就是O(n).
O(n log n) 时间内的第一个 运行s，因为 print(n) 输出 O(log n) 数字。
第二个程序假定了 n 的上限，因此是普通的 O(1)。当我们进行复杂性分析时，我们假设了一个更抽象的编程语言版本，其中（通常）整数是无界的，但算术运算仍在 O(1) 中执行。在您的示例中，您将实际的编程语言（具有有界整数）与这个更抽象的模型（没有）混合在一起。如果重写程序 [*] 使其具有可动态调整的循环数，具体取决于 n（因此，如果您的数字 n 有 k 位，则有 k+1 嵌套循环），那么它会对最内层代码执行一次迭代从 0 到 n 之后的下一个 10 次方的每个数字。内部循环在构造字符串时执行 O(log n) 工作[**]，因此整个程序也是 O(n log n)。
[*] 您不能使用 for 循环和变量来执行此操作；你必须使用递归或类似的东西，以及一个数组而不是变量 i, j, k, ..., z.
[**] 假设您的编程语言优化了 k 个长度为 1 的字符串的加法，以便在 O(k) 时间内完成 运行s。明显的字符串连接实现将是 O(k^2) 时间，这意味着您的第二个程序将在 O(n(log n)^2) 时间内 运行。
我最近了解了算法的正式 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)。代码中是否有任何导致这种情况发生的原因，或者仅仅是我的示例的荒谬性 "breaks" 数学？
在 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)；证明留给 reader 作为练习）。
在分析算法的 运行 时间时，要寻找的一个关键因素是循环。在算法 1 中，您有执行 n 次的代码，使得 运行time O(n)。在算法 2 中，您有每个 运行 10 次的嵌套循环，因此您的 运行 时间为 O(10^3)。这是因为对于中间循环的每个 运行，您的代码 运行s 最内层循环 10 次，而最外层循环的每个 运行 又 运行s 10 次.所以代码运行s 10x10x10次。 （然而，这纯粹是一个上限，因为您的 if 语句可能会在循环完成之前结束算法，具体取决于 n 的值）。
要在countUp2中计数到n，则需要与n中的位数相同的循环次数：因此log(n)次循环。每个循环可以运行10次，所以总的迭代次数是10^log(n)也就是O(n).
O(n log n) 时间内的第一个 运行s，因为 print(n) 输出 O(log n) 数字。
第二个程序假定了 n 的上限，因此是普通的 O(1)。当我们进行复杂性分析时，我们假设了一个更抽象的编程语言版本，其中（通常）整数是无界的，但算术运算仍在 O(1) 中执行。在您的示例中，您将实际的编程语言（具有有界整数）与这个更抽象的模型（没有）混合在一起。如果重写程序 [*] 使其具有可动态调整的循环数，具体取决于 n（因此，如果您的数字 n 有 k 位，则有 k+1 嵌套循环），那么它会对最内层代码执行一次迭代从 0 到 n 之后的下一个 10 次方的每个数字。内部循环在构造字符串时执行 O(log n) 工作[**]，因此整个程序也是 O(n log n)。
[*] 您不能使用 for 循环和变量来执行此操作；你必须使用递归或类似的东西，以及一个数组而不是变量 i, j, k, ..., z.
[**] 假设您的编程语言优化了 k 个长度为 1 的字符串的加法，以便在 O(k) 时间内完成 运行s。明显的字符串连接实现将是 O(k^2) 时间，这意味着您的第二个程序将在 O(n(log n)^2) 时间内 运行。