有人可以在我的例子中向我解释计算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)次.

它是连续整数的总和.

而且,在你的情况下,它(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².