Big-O 表示法中的嵌套循环？

Question

也许我对 Big-O 符号的理解有误（我已经有一段时间没有学习算法课程了），但以下内容对我来说从来没有太大意义：

这将被视为 O(n^2)：

for (int i = 0; i < num_1; i++)
{
    for (int j = 0; j < num_2; j++) 
    {
        cout << i << " " << j << endl;
    }
}

这将被视为 O(n)：

for (int z = 0; z < num_3; z++) { cout << z << endl; }

我的问题是当涉及到实际条款时。让我们假设num_1 = 10; num_2 = 20; num_3 = 1000;。在这种情况下，第一个示例 O(n^2) 将比 O(n) 第二个示例运行的内部迭代少得多。

更笼统地说：num_3 > num_1 * num_2那么 O(n^2) 片段的效果小于 O(n) 片段。在实际应用中，这两个片段，可以做两个那里有功能上的界限非常独立的任务num_1，num_2和num_3有相当大的不同。嵌套num_1和num_2可能在 0 到 255 之间循环变量值，但num_3可能频繁出现超过一百万的值。

当不考虑实际或操作变量边界时，为什么编码人员应该/会信任基于 Big-O 符号的算法或代码片段？

Answer 1

O(n^2)只有在明确“n”应该是什么的情况下，才说某事是有意义的。通常它指的是输入的大小（或者如果输入是一个数字，它只是指那个数字），但是在您的代码中，不清楚输入是什么。

for (int i = 0; i < num_1; i++)
{
    for (int j = 0; j < num_2; j++) 
    {
        cout << i << " " << j << endl;
    }
}

通常人们会说上面的代码片段的运行时间在O(num_1 * num_2). 如果num_1和num_2都是常量，这意味着它在 中O(1)。如果num_1和num_2都与程序输入的大小 ( n)成线性比例，则确实是O(n^2)。如果num_1和num_2都与输入大小的平方成正比，则为O(n^4)。

底线：这完全取决于它们是什么num_1、num_2是什么、如何以及它们增长的因素。

for (int z = 0; z < num_3; z++) { cout << z << endl; }

现在这段代码在O(num_3). 要说这是什么，n将再次需要我们知道num_3与n.

如果所有num_1、num_2和num_3都与 成线性比例n，那么您确实可以说第一个片段按O(n^2)时间运行，第二个片段在O(n). 然而，在那种情况下，不可能num_3大于num_1 * num_2足够大n。