logo标签列表

计算大O复杂度

javabig-otime-complexity
3

我最终会给这个程序一个包含60,000张400像素图像的输入文件，因此我正在尝试了解这段代码在大量输入时的运行情况。为了易读性，我用“blah”替换了不重要的内容，并将所有ArrayList名称更改为简单的字母（nn、mm和kk）。

        for (Perceptron P : nn){
            //blah
        }
        for (Perceptron P : mm) {
            //blah
        }
        for (Perceptron P : kk){
            //blah
        }

        for (Perceptron P : mm) {
            for (int i = 0; i < nn; i++) {
                //blah
            }
            for (int j = 0; j < kk; j++){
                //blah
            }
        }

        for (Perceptron X : nn){
            for (Perceptron Y : mm){
                //blah
            }
        }

        for (Perceptron Z : kk){
            for (Perceptron Y : mm){
                //blah
            }
        }

我认为答案是O（nn+mm+kk+mm（nn+kk）+nnmm+kkmm）。如果我知道nn是400，mm是300，kk是10，那么这就是O（246710）。但现在我卡住了。我不知道O（246710）是什么意思。我必须只针对其中一个变量计算大O吗？如果是这样，那有什么好处呢？我只是想知道它的性能如何。谢谢
3
你完全不理解Big-O是什么意思。我建议你看一下教程，比如这个：http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html - PM 77-1
O(nn+mm+kk+mm(nn+kk)+nnmm+kkmm) 是 O(mmnn+mmkk+nnmm+kkmm) ，也就是 O(mmkk+nnmm)。所以，这告诉你的是 mm 是最重要的因素 - 它会乘以两个参数。而 kk 和 nn 则相对不那么重要，它们只会各自乘以它们的因子。 - Boris the Spider
7个回答
4

大O符号只关注运行时间中最大的项，本例中为O(mm*(nn+kk))。生成该项的代码部分是以下嵌套循环：

for (Perceptron P : mm) {
    for (int i = 0; i < nn; i++) {
        //blah
    }
    for (int j = 0; j < kk; j++){
        //blah
    }
}

如果您向我们透露kk、mm和nn与实际图像尺寸的关系，我们可以用更有意义的术语给出运行时间的范围。

1

O(N)表示程序的执行时间与N成线性比例关系。因此，O(246710)并没有实际意义。

你的程序的复杂度实际上是O(mm*(nn+kk))。这并不能告诉你在特定输入大小下它需要多长时间才能执行（为此，你需要知道所有单个操作所需的时间），只能告诉你，例如如果mm的大小翻倍，而其他条件保持不变，那么你的程序将需要大约两倍的执行时间。

1
使用算法的运行时间分析，您有最坏情况、平均情况和最佳情况，然而算法的顺序比处理器的速度更重要。这与算法执行的操作数量（也称为n）有关。

以下是使用大O符号的几个示例：

线性：60n + 5或O(n)。这意味着它需要n个操作，常见于循环中。

二次方： 2n^2 + 2n或O(n^2)。这在嵌套循环中很常见。

对数：n的数字位数或O(1)。这用于字典，并且会在非常少的操作后访问元素。（尝试记住在适用的情况下应用此方法以提高性能。）

不，使用大O表示法时我们考虑的是最坏情况运行时间。最好情况运行时间应该使用大Ω表示法。 - Boris the Spider
嗨，我很好奇为什么这个图表仍然有这些算法按照它们的最佳、最差、平均情况推导的列举，特别是排序方面。在这里使用大O进行时间复杂度分析与使用大Omega有何区别？也许实际上存在一个在大O范围内的“最佳情况”？这里的所有最佳情况都真的只是大Omega吗？（根据您的评论还更新了答案） - James Kirsch
@BoristheSpider，你的链接与你的观点相矛盾。大O表示渐进上界，而不是最坏情况下的运行时间。请阅读“不要混淆！”部分。 - fgb
1

大O符号表示输入大小趋近于无穷大时的时间。

首先，您需要确定输入变量。在您的示例中，nn、mm和kk是输入变量。

然后我们计算需要执行多少次迭代：

nn + mm + kk + mm(nn + kk) + nn + kk

简化：
2nn + 2kk + mm(nn + kk + 1)

我们有三个术语，但随着所有的东西进入无限，只有具有最高渐近增长阶的术语才是重要的，即mm(nn + kk + 1)。您应该真正检查渐近阶，因为在此答案中解释它会太长了。
我们将mm(nn + kk + 1)简化为mm(nn + kk)，因为当它趋于无穷大时，一个常数不重要（不会缩放）。
现在我们有mm(nn + kk)，在这里我们从nn和kk中选择增长更快的一个，如何知道哪个增长更快？这取决于您的输入。假设我们选择nn，那么我们就有O(mm*nn)。它属于O(n^2)类别。
1
大 O 并不是你想象中的那样使用。它用于确定最坏情况。如果 nn、mm、kk 都是线性存储的，且不嵌套，则简单地为 O('the-largest-chain')。现在我们不知道 nn、mm 和 kk 之间的关系，所以我能告诉你的最好的是；由于你从未将它们与自身嵌套，因此它是线性的。
两个快速示例展示其作用。 输入： 
int[] arr = {1,2,3}

例子 #1
for (int i : arr) {
    // do something
}

在这种情况下，Big-O简单地为O(n)，因为您只需要从数组的开头到结尾进行迭代，它与元素成正比。 示例#2 
for (int i : arr) {
    for (int j : arr) {
        // do something
    }
}

现在输入和算法之间的关系是二次的，这给出了O(n2)。
我建议阅读此处或者跟随教程，因为它可以比我的回答更清晰地解释。
在你的情况下，你从未嵌套输入，并且没有给定变量之间的直接关系，那么Big-O将简单地将它们相加。在你的情况下应该是O(mm(nn+kk))。
0

大O表示法应该降至算法的最坏情况分母，假设所有输入大小都趋近于无限。

因此，您的表达式 O(nn+mm+kk+mm(nn+kk)+nnmm+kkmm) 应简化为 O(mmnn+mmkk)。

0

我认为你对于复杂度表达式 O(nn+mm+kk+mm(nn+kk)+nnmm+kkmm) 的确切表述是正确的。它测量了变量的复杂性变化，因此不要用值替换变量，在你的情况下当 nn = 400，mm = 300，kk = 10 时，可以简化为 O(nnmm) 或 O(nnnn)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接