logo标签列表

为什么插入排序的最优情况是O(n)，而不是O(n^2)？

algorithmsorting
11

我很难理解为什么插入排序的最佳情况是O(n)？

     for (int i = 0; i < size; i++) {

                for (int j = i; j > 0; j--) {
                    int k = j-1;
                        if( a[j] < a[k]){
                            int temp = a[j];
                            a[j] = a[k];
                            a[k] = temp;
                        }

                }
     }

让我们考虑一个初始数组 [1,2,3,4,5] 大小为 5 第一次循环将从 i = 0 到 size - 1 第二个循环将从 i 到 1，但假设内部 for 循环也从 0 到 size - 1，换句话说，内部 for 循环也会执行 (n-1) 次，类似于外部 for 循环 我同意没有交换，但会有比较，它将与未排序的数组完全相同 ? 那么 n-1(外部循环) * n - 1(内部循环) = n^2 - n + 1 = O(n^2)
有人能解释一下我哪里错了吗？

计算最佳情况的复杂度根本没有任何有用的应用。话虽如此，当数组已经排好序时，您的算法会浪费时间。您可以每次跳过内部循环，只要 a[i+1]>=a[i]。 - n. m.
@n.m.，你说最佳情况没有应用，可能是因为在随机数据中很少出现最佳或接近最佳的情况，但是你接着建议进行代码更改，这只有在这种数据情况下才有意义。有些情况下，人们期望数据几乎按排序顺序排列，在这种情况下，运行时间将更接近于O（N）而不是O（N ^ 2）。 - Richard
谢谢大家，我现在明白了，我之前犯了错误。 - zukes
6个回答
7
起初，这似乎不是一个适合插入排序的代码。看起来你在相反的方式中使用冒泡排序代码。
在插入排序代码中，你不会用每个落在它前面的大元素替换小元素，而是我们浏览所有落在它前面的大元素，只有当我们到达没有元素或没有更多大元素的点时，我们才将小元素放置在那个位置并移动其它所有后续元素。
作为O(n)时间的一部分：
让我们考虑一个已经排序好的五个元素的数组 - arr[11,13,15,17,19]。我们从第一个位置元素移动到最后一个位置。
步骤1：取元素11，因为它是第一个元素，所以我们保持原样。
步骤2：取元素13，查找落在它前面的元素（即元素11），因为13>11，所以不需要再查找在11之前的元素了。
步骤3：取元素15，查找落在它前面的元素（即元素13），因为15>13，所以不需要再查找在13之前的元素了。
步骤4：取元素17，查找落在它前面的元素（即元素15），因为17>15，所以不需要再查找在15之前的元素了。
步骤5：取元素19，查找落在它前面的元素（即元素17），因为19>17，所以不需要再查找在17之前的元素了。
正如我们看到的，对于五个已排序的元素，我们仅需要5次比较，因此对于'n'个已排序的元素，我们仅需要O(n)次比较。

希望上述例子澄清了你的疑惑。
6

你的代码总是在O(n^2)的时间复杂度下运行。你需要在找到元素应该插入的位置时打破内部for循环。

2
考虑以下插入排序的实现方式：
    for (i=1; i<n; i++) {
        j=i;
        while ((j>0) && (s[j] < s[j-1])) {
            swap(&s[j],&s[j-1]);
            j = j-1;
        }
    }

任何排序算法的最佳情况是输入已经按顺序排列。在这种情况下，while循环中的条件始终返回false，因此它只对外部for循环进行迭代，在线性时间内以O(n)时间复杂度完成工作。
1

这里是一种实现插入排序的方法。

取一个输入列表和一个最初为空的输出列表。

遍历输入列表，并将每个项目放置在输出列表上的适当位置。通过遍历输出列表，从第一个元素开始找到适当的位置。

现在，如果您的输入已经排序，则插入点始终位于输出列表的开头或结尾。第一种可能性对应于最佳情况；第二种对应于最坏情况。

例如，我的输入数据是：4 3 2 1。

然后输出列表构建为：

4
3 4
2 3 4
1 2 3 4

由于查看第一个元素仅需要O(1)的时间，因此时间复杂度取决于输入的大小，即为O(N)。

他正在使用一个数组，而不是一个列表。 - Gumbo
1
这里的区别相当微不足道，@Gumbo。 - Richard
插入排序的最佳情况是值已经按升序排列。而您所描述的是它的最坏情况，每次插入一个值时，之前插入的所有值都必须被移动，这会导致 Ο(n^2) 的时间复杂度。 - Gumbo
我在这里描述的是一种插入排序，它与您熟悉的实现方式相反；它并没有显著改变算法，但使其更易于解释。 - Richard
0
将您的方法更改为具有此中断条件，您将获得最佳情况下的复杂度为O(n)。
    void insertionSort0(List<Integer> list)
{
    int loop=0;
    for(int i=1;i<list.size();i++)
    {
        int target=(Integer)list.get(i);
        int pos=0;

        for(int j=i-1;j>=0;j--)
        {
            loop++;
            if((Integer)list.get(j)>target)
            {
                list.set(j+1, (Integer)list.get(j));
                pos=j;
            }
            else
            {
                break;
            }


        }


            list.set(pos, target);

    }
    System.out.println("loop in for insertion sort" +loop);
}
0
最优情况也在Ω(n)中，因此也在Θ(n)中。 - Gumbo
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接