计算大 O 复杂度

Question

我最终会为这个程序提供一个包含大约 60,000 张 400 像素图像的输入文件，因此我试图了解这段代码将如何运行处理大量输入。为了便于阅读，我用 "blah" 替换了不重要的内容，并用简单的字母（nn、mm 和 kk）替换了所有 ArrayList 名称。

        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？如果是这样，那有什么好处？我只是想了解这将如何执行。谢谢

Answer 1

Big-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 与图像实际大小的关系，那么我们可以给您一个运行更有意义的时间。

Answer 2

假设所有输入大小都趋于无穷大，大 O 表示法应简化为算法的最大最坏情况分母。

所以你的表达式 O(nn+mm+kk+mm(nn+kk)+nnmm+kkmm) 应该减少到 O(mmnn+mmkk)。

Answer 3

O(N)表示程序的执行时间与N成线性比例。所以，O(246710)并没有什么意义。

你程序的复杂度其实是O(mm*(nn+kk))。这并没有告诉你任何关于特定大小的输入需要多长时间的信息（为此，你需要知道所有单独的操作需要多长时间），只是如果 mm 翻倍，而所有其他条件保持不变，那么您的程序将花费大约两倍的时间来执行。

Answer 4

Big O 的使用方式并不完全像您想象的那样。它用于确定最坏情况。现在如果nn、mm、kk在数据存储上都是线性的，而non-nested那么就是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)。

我推荐 read over here，或者学习教程，因为它比我的回答更清楚。

在您的情况下，您永远不会嵌套输入，并且由于没有给出变量之间的直接关系，因此 Big-O 将只是将它们相加。在你的情况下应该是 O(mm(nn+kk))。

Answer 5

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

Answer 6

通过运行算法的时间分析，您有 Worst-Case, Average-Case, and Best-Case 个场景，但是 算法的顺序 比处理器的速度更重要.这与算法执行的 操作数 有关。（也记为 n ）

以下是一些使用 Big-O-Notation 的示例：

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

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

对数：number of digits in n 或 O(1)。这在字典中使用，并且将在很少的操作后访问一个元素。（尝试并记住在适用的情况下将此应用于性能。）

Answer 7

Big-O 符号代表输入大小的时间，当大小变为无穷大时。

首先，你必须决定输入变量。在您的示例中，nn、mm 和 kk 是输入变量。

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

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

简化：

2nn + 2kk + mm(nn + kk + 1)

我们有 3 个项，但由于所有项都趋于无穷大，只有具有最高 asymptotic order of growth 的项才有意义，即 mm(nn + kk + 1).你真的应该检查渐近阶，因为在这个答案中解释它太长了。

我们将 mm(nn + kk + 1) 简化为 mm(nn + kk) 因为当它趋于无穷时，a常数数无关紧要（不缩放）。

现在我们有 mm(nn + kk)，在这里我们 select 在 nn 和 kk，怎么知道哪个增长快？这取决于您的输入。假设我们 select nn，那么我们有 O(mm*nn)。属于 O(n^2) 类别。

计算大 O 复杂度

Calculate Big-O Complexity

java

big-o

time-complexity