环路的顺序和增长功能

Question

我想在一个函数中找到这个 for 循环的顺序和增长函数，这个函数接收一个长度为 n > 2.本函数按升序排列数组。

这个函数按照升序对数组进行排序。我试图找到最坏情况下的排序方式：当数组最初是按降序排序的，因此函数必须多次迭代数组以进行排序。

这是一个循环。

        for (int next = 1; next < array.length; next++) {
            int value = array[next];
            int index = next;
            while (index > 0 && value < array[index - 1]) {
                array[index] = array[index - 1];
                index--;
            }
            array[index] = value;
        }

我一直在绞尽脑汁地想办法解决这个问题。写测试，写了大量的函数下来，我很接近，但从来没有对上。如何通过这样的循环来找到它的顺序和增长函数？

任何方向都会非常感激。非常感谢您。

Answer 1

让n是数组的长度。这个循环的最坏情况下运行时间为O(n^2)。简单的方法如下。

当next=1时，while循环的操作次数最多为1 当next=2时，操作次数最多为2，以此类推，直到next=(n -1). 我们可以忽略for循环所做的其他操作，因为它们构成了与增长无关的低阶项。

所以现在，操作的次数是k * (1 + 2 + 3 + 4 +...) = (n - 1)。+ (n - 1))=k*(n*(n - 1)2)=k。n^2 - kn2，其中k是一个常数因子。

因此，函数的增长率为n^2阶。

编辑。

为了解决这个问题，我们通常不计算... 总 语句的数量，因为没有标准。

例如，你会把跟随循环的一次迭代算作一条语句（一条打印语句）还是两条语句（打印语句和增量i）？

for (int i = 0; i < n; i++)
{
    print(i);
}

此外，坦率地说，这不是一个非常有用的度量标准。在大多数情况下，我们只关心算法的最高阶项。

然而，为了回答你的问题，我会把循环算作执行这许多条语句：2n^2 + 2n - 3。