java - 这段代码的复杂性是多少？我必须使用什么符号？

Question

当我确定像这样的 Java 代码的复杂性时，我是否必须用 Theta 或大 O 表示法来表达？

List<Person> sortedPersons = new ArrayList<Person>();
List<Person> people = new ArrayList<Person>();

    for (int i = 0; i < people.size(); i++) {
        Person toadd = people.get(i);

        int index = 0;
        while(index < sortedPersons.size() && sortedPersons.get(index).compareTo(toadd) < 0)
            index++;

        sortedPersons.add(index, toadd);

    }

我知道 for 循环的复杂度是 O(n) (或者是\Theta(n)？)get 操作以常数时间运行，因此 O(1)。但是 while 循环呢？SortedPersons.size(): O(1)SortedPersons.get(): O(1)CompareTo 操作是线性的吗？我认为加法操作也以恒定的时间运行。代码的总复杂度是多少？

Answer 1

代码复杂度为 O(n²)如果您考虑数字并将它们从小到大排序。

• 如果您的输入是反向排序(从大到小)，则代码将为 θ(n)。
• 如果您的输入已排序，则此代码将为 Θ(n²)

该代码只是 Insertion sort 的变体，它只是使用列表而不是数组。

考虑这个例子的复杂性:

数字是 1 2 3 4 5，您想要从小到大排序。

1. 第一次迭代后，你的列表将包含 1。(这发生在 o(1) 中)，你赢了t 访问内循环。
2. 在第二次迭代中，您将获得一个 { 1 } 列表，因为您要插入 2，因此您将访问 while 循环一次，然后再将其插入。
3. 第三次迭代时列表为 { 1 2 }，您访问 while 循环两次并在其后插入 3。
4. ...

最后你会得到类似的东西:0 1 2 3 4 次访问内循环。

现在您可以将 1 2 3 4 5 写为 (5(5+1))/2)。

现在您可以将 O(n(n+1)/2 + n) 写为 O(n²)。