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).后者只是一个数字.前者是一种功能.

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