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

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

因此,如果咖啡总是需要5分钟,那么计算大O解决方案的信息就不够了,但是如果需要5分钟来制作咖啡,5分钟可以制作10个咖啡,5分钟可以赚到100万个咖啡咖啡,那么它是O(1),其中1表示一个时间单位.

现在,如果你有一个单杯咖啡机,大约需要两分钟来制作一杯咖啡,四分钟可以制作两杯咖啡,二十分钟可以制作十杯咖啡,那么现在是时候制作一杯咖啡了.咖啡与杯子的数量成正比,使得大O符号O(x),意味着您需要X(每个咖啡一个)时间单位.

其他大O符号是常见的,O(x ^ 2)O(xlog(x))等.它们都描述了基于所考虑的元素数量的比例时间增加率.

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