Big O - 适合新手

Question

可能的重复：
Big O 的简单英语解释

最近有人问我关于如何使用 Big O 表示法，我被难住了，因为我以前从未遇到过 Big O。我已阅读关于 Big O 的维基百科页面，并查看了 Stackoverflow 中发布的一些问题，但是我只是不明白。

我的问题：有人可以以最简单的形式提供 Big O 的解释，并提供如何在以下 Java 方法中使用它的示例：

public int getScore(int[] dice)
{
    int[][] dups;

    dups = possibleDups(dice);

    // Set catScore
    for (int[] i : dups)
    {
        for (int k = 0; k < i.length; k++)
        {
            if (i[k] > 0)
            {
                switch (i[k]) {
                case 1:
                    catScore = Category.ONES;
                    break;
                case 2:
                    catScore = Category.TWOS;
                    break;
                case 3:
                    catScore = Category.THREES;
                    break;
                case 4:
                    catScore = Category.FOURS;
                    break;
                case 5:
                    catScore = Category.FIVES;
                    break;
                case 6:
                    catScore = Category.SIXES;
                    break;
                case 7:
                    catScore = Category.SEVENS;
                    break;
                case 8:
                    catScore = Category.EIGHTS;
                    break;
                default:
                    catScore = Category.NONE;
                    break;
                }
            }
        }
    }

    return sumAll(dice);
}

Answer 1

大 O 表示法详细说明了解决方案的时间与集合中的项目数相比的比例差异。它实际上没有说明解决方案需要多长时间来解决问题，但它详细说明了当您知道固定点的时间以及可能添加的其他项目的数量时，解决解决方案的时间增长的速度。

因此，如果煮一杯咖啡总是需要 5 分钟，则没有足够的信息来计算 Big O 解决方案，但如果煮一杯咖啡需要 5 分钟，煮十杯咖啡需要五分钟，煮一百万杯咖啡需要五分钟咖啡，那么它是 O(1)，其中 1 表示一个时间单位。

现在，如果您有一台单杯咖啡机，制作一杯咖啡大约需要两分钟，制作两杯咖啡需要四分钟，制作十杯咖啡需要二十分钟，那么制作许多咖啡的时间咖啡的数量与杯子的数量成正比，形成大 O 表示法 O(x)，这意味着您需要 X（每杯咖啡一杯）时间单位。

其他 Big O 表示法也很常见，例如 O(x^2) O(xlog(x)) 等。它们都描述了基于所考虑的元素数量的时间增长比例。

请注意，对于某些小型项目集合，O(1) 可能比 O(x) 解决方案慢，因为我们讨论的是时间单位，而不是实际时间。因此，特定 O(1) 中的时间单位可能是一小时，而 O(x) 解决方案中的特定时间单位可能是十分钟。在这种情况下，O(x) 解决方案可能会更快，直到您需要处理六个或更多项目。从长远来看，无论实际时间单位有多大或多小，具有较低幂（例如 O(1)）的大 O 项将始终优于具有较高幂 O(x) 的项。

Answer 2

Big O 是算法执行的最坏情况。您应该看到循环如何依赖于内部循环。示例：

public void doSomething(int n){
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
}

最坏的情况是迭代 100 次。将n更改为20，那么最坏的情况是400次迭代。

这是 O(n^2)。

Answer 3

在计算机科学中，人们感兴趣的一大领域是“事物运行需要多长时间？”。很多时候答案是“这取决于输入的大小（但也可能不是）”。 Big-Oh 具体来说是一个描述算法运行时间上限的函数。其中有一些数学细节（极限、渐近线等），但那是一个非常基本的视图。

在您的示例中，您循环遍历一个列表，然后对于该列表中的所有内容，您循环遍历另一个列表。因此，算法运行所需的时间与列表的大小成正比。如果你认为一个列表中有“n”个东西，而你的第二个列表中有 m 个东西，那么你的算法的运行时间是 O(m*n)。如果m ~ n，那么准确地说O(n^2)也是正确的。

对于地图，查找的时间是恒定的（假设是）。在这种情况下，Map 查找的运行时间为 O(c)，与 O(1) 相同。