c# - 有人可以在我的例子中解释一下计算 big-O 的逻辑吗

Question

据说选择排序的复杂度是 O(N^2)，但我不明白其中的逻辑，因为我正在减少循环执行的次数。我理解代码块 2 但不理解代码块 1

public int[] Sorting(int[] array)
{
    for (i = 0; i <= array.Length - 1; i++)
    {           
        minimum=i;
        for (j = i; j < array.Length-1; j++) 
        {
            if (array[minimum] > array[j+1])
                minimum = j + 1;
        }   
        int temp = array[minimum];
        array[minimum] = array[i];
        array[i] = temp;
    }

    return array;
}

---

for(i=0;i<=n;i++) //Code 2
{
    for(j=0;j<=n;j++)

Answer 1

设n 为数组大小。

并查看比较次数(调用 if (array[minimum] > array[j+1]))。

• 对于 i=0 它被调用了 n-1 次。
• 对于 i=1 它被调用了 n-2 次。
• ...
• 对于 i=n-1 它被调用了 0 次。

最后，它被调用了 0+1+...+(n-1) 次。

这是sum of consecutive integers .

并且，在您的情况下，它是 (n-1)*n/2，即 O(n²)

编辑:

所以准确的比较次数是(n-1)*n/2，不完全是n²，比n²好看>，但事实并非如此。

• 对于 n=10，您有 45 次比较。
• 对于 n=100，您有 4950 次比较。

也就是说，输入次数增加 10 次，您需要花费 > 100 次以上的时间来完成您的算法。

• 对于 n=10，您有 45 次比较。
• 对于 n=1000，您有 499500 次比较。

也就是说，输入次数增加 100 次，您需要花费 > 10 000 次以上的时间来完成您的算法。

如您所见，当您将条目数乘以 k 时，您将粗略地乘以 k² 计算时间。