小编Mum*_*mfi的帖子

问题很简单,但我找不到足够好的答案.在关于大O符号最upvoted SO问题,它说:

例如,通常基于比较操作来比较排序算法(比较两个节点以确定它们的相对排序).

现在让我们考虑一下简单的冒泡排序算法:

for (int i = arr.length - 1; i > 0; i--) {
    for (int j = 0; j < i; j++) {
        if (arr[j] > arr[j+1]) {
            switchPlaces(...)
        }
    }
}

我知道最坏的情况是O(n²)最好的情况O(n),但究竟是n什么？如果我们尝试对已经排序的算法进行排序(最好的情况),我们最终什么都不做,那么为什么它仍然存在O(n)呢？我们仍在循环2个for循环,所以如果它应该是什么O(n²).n不能进行比较操作的次数,因为我们还是比较所有的元素吧？