java - 衡量一些排序算法的时间复杂度

Question

我正在用 Java 编写一个演示类来分析以下排序算法:

1. 插入排序
2. 选择排序
3. 冒泡排序
4. 合并排序
5. 快速排序

我在另一个名为 Sort 的类中将其实现为静态方法。

我想通过使用 omicron 公式确定具有分析复杂性的运行时间来比较每个算法的最佳、平均和最差情况。

在演示课中，我只想确定每个算法需要的时间(以纳秒为单位)，以数组中数字的最佳、平均和最差顺序对具有不同长度的整数数组进行排序。

        //Best-Case
    int[] arrbc0 = {1};
    int[] arrbc1 = {1, 2};
    int[] arrbc2 = {1, 2, 3};
    int[] arrbc3 = {1, 2, 3, 4, 5};
    int[] arrbc4 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int[] arrbc5 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

    //Average-Case
    int[] arrac1 = {1, 2};
    int[] arrac2 = {3, 1, 2};
    int[] arrac3 = {4, 2, 3, 1, 5};
    int[] arrac4 = {9, 1, 10, 6, 2, 4, 8, 3, 7, 5};
    int[] arrac5 = {13, 12, 1, 15, 5, 6, 7, 2, 14, 10, 3, 8, 4, 9, 11};

    //Worst-Case
    int[] arrwc1 = {2, 1};
    int[] arrwc2 = {3, 2, 1};
    int[] arrwc3 = {5, 4, 3, 2, 1};
    int[] arrwc4 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int[] arrwc5 = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    //InsertionSort:
    isNanoTime(arrbc0); //first load
    isNanoTime(arrbc1);
    isNanoTime(arrbc2);
    //...

    public static void isNanoTime(int[] arr) {
    long a1 = System.nanoTime();
    Sort.insertionSort(arr);
    long a2 = System.nanoTime() - a1;
    System.out.println(a2);
    }

现在我有一些问题:

1. 我可以将这些数组用于这些算法的所有最佳、平均和最坏情况吗？ MergeSort 的最坏情况是另一个订单？!
2. 有没有一种简单的方法可以在对数组进行一次排序后取消排序？
3. 无论如何，这是确定时间复杂度的“正确方法”吗(也许有人有更好的主意)？

Answer 1

1. 你的数组太短了:任何“现代”CPU 几乎都不需要时间来对它们进行排序，即使在最坏的情况下也是如此
2. 要根据输入的随机性获得相关的时间变化，您需要设置一个固定的输入大小，并为您提供可测量的时间(可能以秒为单位)
3. 您可能需要生成一组包含数千个随机数组的集合，可能需要向该集合中添加一些特定数组(排序、反向排序等)。然后，您可以在该集合中的每个数组上运行每个算法，并测量对它们进行排序所需的时间。这样做你可以获得每个算法的一个很好的分布图，你可以在上面看到每个算法的行为(冒泡排序非常高，而堆排序非常稳定......)。一种算法的最差输入不一定与另一种算法相同，因此该集合。