代码之家 › 专栏 › 技术社区 › Mr. Llama

用Big-O表示法嵌套循环?

big-o theory

Mr. Llama · 技术社区 · 14 年前

也许我对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)的内部迭代次数要比第二个示例少得多。

一般来说:当 num_3 > num_1 * num_2 然后O(n^2)代码段的作用小于O(n)代码段。在实际应用程序中,这两个代码片段可能正在执行两个非常独立的任务,其中 num_1 , num_2 ,和 num_3 有很大的不同。嵌套的 数字1 和 数字2 可能在0到255之间循环变量值,但是 数三 可能经常值超过一百万。

为什么一个编码者应该/会信任一个基于其Big-O符号的算法或代码片段而不考虑 实际的 或 操作的 可变边界?

6 回复 | 直到 14 年前

sepp2k 14 年前

说有东西在里面 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) . 如果两者都是 数字1 和 数字2 与程序输入的大小成线性比例( n ),确实是 O(n^2) . 如果两者都是 数字1 和 数字2 与输入大小的平方成正比 O(n^4) .

一句话:这完全取决于 数字1 和 数字2 是、如何以及取决于它们生长的因素。

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

现在这个代码在 O(num_3) . 说这是什么 n个 会再次要求我们知道 num_3 与 n个 .

如果所有的 数字1 , 数字2 和 数三 与 n个 ,那么您确实可以说第一个片段 O(n^2) 时间和秒 O(n) . 但是在这种情况下 数三 大于 num_1 * num_2 足够大的 n个 .

Byron Whitlock 14 年前

大O描述的是算法速度,而不是实际代码。

当你有一个通用算法时,你不知道变量的约束是什么。

Peter G. McDonald 14 年前

大OH符号是将计算复杂度表示为增长函数的一种方式。必须理解的是,它是一个近似值,它只对所涉及的变量的较大值(如n)作出让步。

您绝对正确,单个变量值、常量等都会产生很大的影响。

然而,对于相似(和较大)大小的变量值,一组算法的大Oh表达式将指示它们的相对性能。更典型的是,它是一种方便的实现方式,独立地表示算法的最佳、平均和最坏情况复杂度。

然而,在一天结束时,一旦选择了一个候选算法的短列表(可能基于大的oh符号和其他特性,如空间需求等),那么用一个有代表性的数据集对一个实现进行计时是一条路要走。

Marek Sapota 14 年前

大O符号只表示算法对给定数量级的数据工作多长时间,以及当您获得更多数据时它将如何“缩放”,O(n)算法如果获得的数据比O(n^2)算法慢(如您在示例中所示)。但是如果你给一个O(n)算法输入2倍多的数据,你应该期望运行时间延长2倍,而使用O(n^2),你应该期望运行时间延长4倍。

Brent Writes Code 14 年前

当N接近无穷大时,你可以为这些例子考虑大O。

因此,在您的场景中,num嫒3>num嫒1*num嫒2是正确的,但是随着这三个数字越来越大,这将不再适用。

如果algorithm1是O(N),algorithm2是O(N^2),并不意味着algorithm1总是比algorithm2好,它只是意味着N有一个阈值(通常称为N0),在这个阈值之后,algorithm1将比algorithm2好。

一个随机的例子是插入排序是O(N^2),其中MergeSort是O(N*log(N)),但是对于非常小的N值,插入排序实际上会更快。一旦N足够大,MergeSort总是更快。Java版本的 Arrays.sort 函数实际上有一个 if 语句,对非常小的N值使用插入排序,对大于特定大小的任何值使用修改后的快速排序或合并排序(幻数约为N=7)。

Java代码(在Java6中)用于 数组.sort 为了一个 int 数组如下所示:

private static void sort1(int x[], int off, int len) {
    // Insertion sort on smallest arrays
    if (len < 7) {
           //insertion sort
        }

        //modified quick sort
}

归根结底,Big O notation是一种分类机制,可以帮助您快速分析和比较算法,其方式独立于计算机硬件,不需要编写、测试和计时各种算法的执行。这是一个简化的符号,所以它永远不会是精确的,正如我刚才给出的例子所示,它非常依赖于数据的大小和范围。

算法的大O符号的一个主要警告是,如果您可以对数据进行假设,则通常可以对算法进行改进。

Matt 14 年前

Big-O给出了上限或最坏情况下的增长率。常数被忽略,因为随着n的增长,它们变得越来越不重要(例如,你不说O(3+2n),而只说O(n))。

大欧米茄是一个最好的情况增长率,取决于你知道你的算法将如何使用可能更适合你在某些情况下使用。

如果给定算法的Big-O和Big-Omega是相同的,那么in被称为精确顺序,你可以把它改为大θ。

编辑:为了澄清这一点,最坏情况分析通常更可取,因为您希望能够告诉客户“它总是会表现得很好或更好”,而不是“如果您的数据恰巧是完美的,它会表现得很好!”