java - java中算法的时间复杂度

Question

您好，我正在使用以下通用冒泡排序算法，我想显示时间复杂度。我知道该算法的最佳/最差情况是固定的，但我想知道，它可以特定于我的数组吗？

例如，这种排序的最坏情况是O(n^2)，这可以特定于我的数组吗？

例如，最坏的情况可能是对 120 个元素中的 100 个进行排序(这就是我所说的特定于我的数组的意思)。

public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) {
    boolean changed = false;
    do {
        changed = false;
        for (int a = 0; a < comparable.length - 1; a++) {
            if (comparable[a].compareTo(comparable[a + 1]) > 0) {
                E tmp = comparable[a];
                comparable[a] = comparable[a + 1];
                comparable[a + 1] = tmp;
                changed = true;
            }
        }
    } while (changed);
}

Answer 1

复杂性是函数(或算法)的渐近属性，而不是实际执行路径的渐近属性。复杂性表示输入大小和计算时间(或空间要求)之间的关系。因此，当应用于单个具体计算时，这个概念没有任何意义。

也就是说，你可以询问计算的复杂度f(n)取决于n ，但不是计算的 f(5) 。后者只是一个数字。前者是一个函数。

您可以做的是计算实际操作数。每次执行要包含的操作(例如“比较”)时，只需增加一些全局计数器，然后检查其值。 (算法的复杂性应该告诉您该计数器可能采用的值的界限。)