big-O表示法中的n是什么？

Question

问题很简单,但我找不到足够好的答案.在关于大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不能进行比较操作的次数,因为我们还是比较所有的元素吧？

Answer 1

分析排序算法的Big-O性能时,n通常表示要排序的元素数.

因此,例如,如果您n使用冒泡排序对项目进行排序,则最坏情况下的运行时性能将为O(n ²)次操作.这就是为什么冒泡排序被认为是一种极差的排序算法,因为它不能随着要排序的元素数量的增加而很好地扩展.随着要排序的元素数量线性增加,最坏情况运行时间间隔增加.

下面是一个示例图,演示了随着问题大小N的增加,各种算法如何根据最坏情况运行时进行扩展.深蓝色线表示线性缩放的算法,而品红色/紫色线表示二次算法.

请注意,对于足够大的N,二次算法最终需要比线性算法更长的时间才能解决问题.

图表取自http://science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/.

也可以看看

• Big-O的正式定义.

Answer 2

我认为这里有两件事情变得混乱,n而且其功能n受到Big-O分析的限制.

按照惯例,对于任何算法复杂度分析,n如果没有指定任何不同,则是输入的大小.对于任何给定的算法,输入大小有几个有趣的函数,可以计算渐近边界,如Big-O.

用于排序算法的最常见的这种函数是最坏情况下的比较数.如果有人说排序算法O(n^2)没有指定任何其他内容,我会认为它们意味着最坏情况下的比较计数O(n^2),n输入大小在哪里.

另一个有趣的功能是除了要排序的数组之外的工作空间量,空间量.冒泡排序的工作空间是O(1)恒定空间,因为它只使用一些变量而不管数组大小.

冒泡排序可以编码为仅n-1在最佳情况下进行数组元素比较,通过在没有交换的任何传递之后完成.请参阅此伪代码实现,该实现swapped用于记住是否存在任何交换.如果数组已经排序,则第一遍不进行交换,因此排序在一次通过后结束.