这个程序的Big-O是O(N^2)吗？

Question

我正在阅读 Cracking the Coding Interview（新一期）。该程序似乎运行正确。不过，当我检查它时，答案似乎是 N^2 / 2。我不认为我是对的。谁能告诉我 Big-O 是什么以及为什么？

    class Program
    {
        static void Main(string[] args)
        {
            int userNumber = Convert.ToInt32(Console.ReadLine());
            int[] makeAnArray = new int[userNumber];
            for (var x = 0; x < userNumber; x++)
            {
                makeAnArray[x] = x; 
            }
            DisplayIterations(makeAnArray);
        }
        static void DisplayIterations(int[] testA)
        {
            int totalIterations = 0;
            for (var i = 0; i < testA.Length; i++)
            {
                totalIterations++;
                Console.WriteLine("i is " + i );
                for (var j = i + 1; j < testA.Length; j++)
                {
                    totalIterations++;
                    Console.WriteLine("j is " + j);
                }
            }
            Console.WriteLine("The amount of iterations: " + totalIterations);
        }
    }

基本上，该函数接受一个数组，运行一个 for 数组长度循环和一个 for 循环 length-1。我投入 10 我得到 55。

Answer 1

是的，那个程序的Big-O是O(N^2)。

在 Big-O 表示法中，您仅使用主要因素（例如忽略系数）。

因此，即使您更精确（实际答案是 n(n-1)/2），该符号也会忽略您的 1/2 系数和任何小于 n^2 的因素，这是主导因素。

看到这个答案：

Answer 2

实际迭代次数，其中n为数组大小，为：

n(n+1)/2

可以扩展到

(n^2 + n)/2

然而，在大 O 表示法中，您通常对算法的 class 感兴趣，因为输入大小变大，并且可以忽略常量（例如上面公式中的 2）和变量指数小于最大指数 - 因此您可以忽略 n 分量，因为随着 n 大小的增加，n^2 将很快超过 non-quadratic 分量。因此，您可以将实际操作计数为 (n^2 + n)/ 2 的算法简单地称为 O(n^2).

供参考，这里是 Wikipedia:

中大 O 符号的定义

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

解释你为什么有 n(n+1)/2 个操作：

您正在以下列方式遍历数组：

for (var i = 0; i < arr.Length; i++)
{
    for (var j = i + 1; j < arr.Length; j++)
    {
    }
}

我将用以下符号画出几个例子：

i0 means that your program printed out 'i is 0'
j1 means that your program printed out 'j is 1'

让我们画出您的程序将打印的数组长度为 1 的内容，其中每一行代表外循环和内循环的整个迭代：

i0

现在数组长度为 3:

i0 j1 j2
i1 j2
i2

数组长度为 6:

i0 j1 j2 j3 j4 j5
i1 j2 j3 j4 j5
i2 j3 j4 j5
i3 j4 j5
i4 j5
i5

这样画出来很容易看出，当n = 6时，我们打印出6 + 5 + 4 + 3 + 2 + 1条语句。注意，这只是加法从 1 到 6 的所有整数，或者更一般地说，从 1 到 n。从 1 到 n 的整数总和的众所周知的公式是（惊喜！）(n^2 + n)/2.

我打字有点仓促，但希望你能看到我是如何得出这个结论的。这与您的评估一致，即对于长度为 10 的输入，您有 55 次迭代：(10^2 + 10)/2 = (110)/2 = 55.

这个程序的Big-O是O(N^2)吗？

Is the Big-O of this program O(N^2)?

c#

big-o