java - 创建一个 SortedSet(对象)并向其插入元素或创建一个 ArrayList 并在之后对其进行排序是否更快？

Question

<分区>

Answer 1

这两种方法都在 𝓞(n log(n)) 时间内:将项目添加到 ArrayList 的最坏情况是 𝓞(n)，但通常在常数时间内完成，当后备阵列足够长。实际排序在𝓞(n log(n))中。

根据docs ，将项目添加到 TreeSet 是在 𝓞(log n) 中。你这样做了 n 次，所以总的时间复杂度是 𝓞(n log(n))。

然而 Collections.sort 在实践中似乎更快。

此代码片段打印 timeArray: 380 和 timeTree: 714。

import java.util.Collections;
import java.util.ArrayList;
import java.util.TreeSet;
import java.util.Random;

class Test {
    public static void main(String[] args) {
        int steps = 1000000;    // one million lines

        System.out.print("timeArray: ");
        System.out.println(timeArray(steps));
        System.out.print("timeTree: ");
        System.out.println(timeTree(steps));
    }

    private static long timeArray(int steps) {
        long t1 = System.currentTimeMillis();

        ArrayList<Integer> arr = new ArrayList<>();
        Random rnd = new Random();

        for (int i = 0; i < steps; i++) {
            arr.add(rnd.nextInt());
        }
        Collections.sort(arr);

        return System.currentTimeMillis() - t1;
    }

    private static long timeTree(int steps) {
        long t1 = System.currentTimeMillis();

        TreeSet<Integer> tree = new TreeSet<>();
        Random rnd = new Random();

        for (int i = 0; i < steps; i++) {
            tree.add(rnd.nextInt());
        }

        return System.currentTimeMillis() - t1;
    }
}