大 O 符号中的 n 是什么? [英] What is the n in big-O notation?

问题描述

这个问题很简单，但我找不到足够好的答案.在 关于 big-O 符号的最受好评的 SO 问题 上，它说:

The question is rather simple, but I just can't find a good enough answer. On the most upvoted SO question regarding the big-O notation, it says that:

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

For example, sorting algorithms are typically compared based on comparison operations (comparing two nodes to determine their relative ordering).

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

Now let's consider the simple bubble sort algorithm:

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 不能是比较操作的次数，因为我们还是比较所有的元素吧?

I know that worst case is O(n²) and best case is O(n), but what is n exactly? If we attempt to sort an already sorted algorithm (best case), we would end up doing nothing, so why is it still O(n)? We are looping through 2 for-loops still, so if anything it should be O(n²). n can't be the number of comparison operations, because we still compare all the elements, right?

推荐答案

n 通常是输入的大小.对于数组，这将是元素的数量.

n is usually the size of the input. For array, that would be the number of elements.

要查看不同的情况，您需要更改算法:

To see the different cases, you would need to change the algorithm:

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).

Your algorithm's best/worst cases are both O(n^2), but with the possibility of returning early, the best-case is now O(n).

这篇关于大 O 符号中的 n 是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！