大O表示法中的n是什么？

Question

问题非常简单，但我却找不到足够好的答案。在关于大O符号的最受欢迎的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)呢？我们仍然要遍历两个for循环，所以如果有的话，它应该是O(n²)。n不能表示比较操作的数量，因为我们仍然检查所有元素，对吧？

- Mumfi

---

数组长度为n。即使数组已经排序，你也需要进行n-1次比较来验证。 - Niklas B.

“WC”和“BC”应该是什么？请避免使用不常见的缩写，因为你不能确定人们是否理解它们的含义。 - user456814

假设WC和BC分别代表最坏情况和最好情况，你展示的算法并没有最佳情况O(n)，因为它在发现数组已排序时不会提前退出。 - user2357112

@NiklasB。n是数组的长度吗？怎么可能呢？即使最坏情况下O(n^2)，数组的长度也不会改变啊。 - Mumfi

@eitank那是不正确的。在处理排序算法时，N代表要排序的元素总数。您访问内存的次数将是一个函数f(n)，即N的函数。 - user456814

@Mumfi，请查阅大O符号的正式定义。 - user456814

Answer 1

在分析排序算法的大O性能时，n通常表示您要排序的元素数量。

例如，如果您使用冒泡排序对n个项目进行排序，则最坏情况下的运行时间性能将按照O(n²)操作的顺序进行。这就是为什么冒泡排序被认为是一种极差的排序算法，因为它无法随着需要排序的元素数量的增加而良好扩展。随着需要排序的元素数量的线性增加，最坏情况下的运行时间将呈二次方增长。

以下是一个示例图表，演示了随着问题大小N的增加，各种算法在最坏情况下的运行时间如何扩展。深蓝色线条表示按线性比例扩展的算法，而品红/紫色线条则表示二次算法。

请注意，对于足够大的N，二次算法最终需要更长的时间来解决问题。

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

参见

• Big-O的正式定义。

- user456814

---

那么这只是用于排序算法吗？这只是一个常见的约定吗？我的意思是，假设你有两个for循环，一个嵌套在另一个中，两个都从0到n，内部for循环之后进行一些加法。O将是（n ^ 2）。那么n是什么？只是+操作的数量吗？ - Mumfi

一般进行大O分析时，N代表问题的规模。在你的双重循环示例中，变量n代表什么？ - user456814

只是一些任意的数字。有点像这样： https://dev59.com/iXRB5IYBdhLWcg3wv5o_ - Mumfi

Answer 2

我认为这里有两件事情被混淆了，n和由大O分析所限制的n的函数。

按照惯例，在任何算法复杂度分析中，如果没有特别指定，n就是输入的大小。对于任何给定的算法，有几个有趣的输入大小的函数可以计算渐近界限，如大O。

排序算法最常见的这种函数是最坏情况下的比较次数。如果有人说一个排序算法是O(n^2)，没有特别说明，我会认为他们的意思是最坏情况下的比较次数是O(n^2)，其中n是输入大小。

另一个有趣的函数是工作空间的大小，即除了要排序的数组之外的空间。冒泡排序的工作空间是O(1)，即常量空间，因为它只使用了几个变量，而不管数组的大小。

冒泡排序在最好情况下可以仅进行n-1次数组元素比较，通过在没有交换的任何一轮之后结束。请参见此伪代码implementation，它使用swapped来记住是否有任何交换。如果数组已经排序，则第一遍不会有任何交换，因此排序只需要一遍即可完成。

- Patricia Shanahan

---

好的回答。然而，我认为原帖作者可能也对冒泡排序的最佳情况运行时间（根据他的说法）在已经排序的数组中为O(n)感到困惑，因为该算法使用了两个嵌套的for循环。或者类似这样的问题。原始问题有点混乱和不清楚。 - user456814

Answer 3

n通常是指输入的大小。对于数组来说，就是元素的数量。

要了解不同情况，需要更改算法：

for (int i = arr.length - 1; i > 0 ; i--) {
    boolean swapped = false;

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

    if(!swapped) {
        break;
    }
}

您的算法最好和最坏的情况都是O(n^2)，但有可能提前返回，因此最好的情况现在是O(n)。

- fgb

---

我会给你最好的答案，因为它只针对并准确地解决了我心中的疑惑。 - Mumfi

Answer 4

n 是数组长度。您想要找到 T(n) 算法复杂度。

访问内存比检查条件要昂贵得多。因此，您定义 T(n) 为访问内存的次数。

在给定的算法中，BC 和 WC 使用 O(n^2) 次访问内存，因为您检查 if 条件 O(n^2) 次。

使复杂度更好：保持一个标志，如果在主循环中没有进行任何交换，则意味着您的数组已排序，可以放置一个 break。

现在，在 BC 中，数组已排序并且您只访问所有元素一次，所以是 O(n)。 而在 WC 中仍然是 O(n^2)。

- eitank

---

但是在已排序的数组情况下，我只需要检查if条件吗？而且我要这样做O(n^2)次！抱歉，还有点困惑。 - Mumfi

使用更高级的冒泡排序版本，以防止不必要的内存访问。 - eitank