algorithm - O(n^2) 或 O(n log n)？

Question

算法

基本上，下面的算法是 O(n log n) 还是 O(n^2)。我确定该算法有一个名字；但我不确定它是什么。

伪代码:

def sort(list):
    dest = new list
    for each element in list (call it a):
        for each element in dest (call it c):
            if a <= c, insert a into dest directly before c
    return dest

在 Java 中:

public static List<Integer> destSort(List<Integer> list) {
    List<Integer> dest = new ArrayList<>();
    for (Integer a : list) {
        if (dest.isEmpty()) {
            dest.add(a);
        } else {
            boolean added = false;
            for (int j = 0; j < dest.size(); j++) {
                int b = dest.get(j);
                if (a <= b) {
                    dest.add(j, a);
                    added = true;
                    break;
                }
            }
            if(!added) {
                dest.add(a);
            }
        }
    }
    return dest;
}

简单地说，该算法遍历一个列表，并将每个元素插入到新创建的列表的正确位置。

复杂性

这就是我对这个算法的复杂性的看法:

• 对于列表中的每个元素，dest 的大小增加 1
• 这意味着，在每个步骤中，算法都有一个大小为 dest 的最坏情况时间
• 将这些加起来，我们会得到 0 + 1 + 2 + 3 + ... + n
• n 以内的所有自然数之和 = n(n+1)/2
• 这简化为 (n^2 - n)/2，通过删除常量和低次项，我们得到 O(n^2)

因此复杂度为 O(n^2)。

不过，我最近在浏览this answer ，其中作者指出:

O(n log n): There was a mix-up at the printer's office, and our phone book had all its pages inserted in a random order. Fix the ordering so that it's correct by looking at the first name on each page and then putting that page in the appropriate spot in a new, empty phone book.

对我来说，这听起来像是同一个算法，所以我的问题是:

• 我描述的算法与@John Feminella 描述的算法相同吗？
• 如果是，为什么我的 O(n^2) 计算不正确？
• 如果不是，它们有何不同？

Answer 1

您描述的算法与链接答案中描述的 O(n log n) 算法不同。实际上，您的算法是 O(n^2)。

关键区别在于确定每个元素的正确位置的方式。在您的算法中，每个元素都按顺序搜索，这意味着您将每个元素与其他每个已排序的元素进行检查。链接算法基于用于查找人名的 O(log n) 方法:

O(log n): Given a person's name, find the phone number by picking a random point about halfway through the part of the book you haven't searched yet, then checking to see whether the person's name is at that point. Then repeat the process about halfway through the part of the book where the person's name lies. (This is a binary search for a person's name.)

如果您使用此方法查找新书中每一页的位置，您最终只会为每一页执行 O(log n) 次操作，而不是像您的算法中那样每页执行 O(n) 次操作。

---

顺便说一句，您描述的算法本质上是一个 insertion sort ，尽管它使用两个列表而不是就地排序。