为什么 big-Oh 并不总是算法的最坏情况分析? [英] Why big-Oh is not always a worst case analysis of an algorithm?

问题描述

我正在尝试学习算法分析，但我对渐近符号(big O...)和cases(最佳、最差和平均)之间的关系感到困惑.

I am trying to learn analysis of algorithms and I am stuck with relation between asymptotic notation(big O...) and cases(best, worst and average).

我了解到 Big O 符号定义了算法的上限，即它定义了函数的增长不能超过其上限.

I learn that the Big O notation defines an upper bound of an algorithm, i.e. it defines function can not grow more than its upper bound.

起初对我来说听起来是因为它计算了最坏的情况.我在谷歌上搜索(为什么最坏的情况不是大 O?)，并得到了很多对初学者来说不太容易理解的答案.

At first it sound to me as it calculates the worst case. I google about(why worst case is not big O?) and got ample of answers which were not so simple to understand for beginner.

我总结如下:Big O 并不总是用来表示算法的最坏情况分析，因为假设一个算法对最佳、平均和最差输入采取 O(n) 执行步骤，那么它的最佳、平均和最坏情况可以是表示为 O(n).

I concluded it as follows: Big O is not always used to represent worst case analysis of algorithm because, suppose a algorithm which takes O(n) execution steps for best, average and worst input then it's best, average and worst case can be expressed as O(n).

请告诉我我是否正确或我遗漏了什么，因为我没有人来验证我的理解.请提出一个更好的例子来理解为什么Big O 并不总是最坏情况.

Please tell me if I am correct or I am missing something as I don't have anyone to validate my understanding. Please suggest a better example to understand why Big O is not always worst case.

推荐答案

Big-O?

首先让我们看看Big O的正式含义:

在计算机科学中，使用大 O 符号对算法进行分类根据他们的运行时间或空间需求如何随着输入大小增加.

In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.

这意味着，Big O 表示法根据函数的增长率来表征函数:具有相同增长率的不同函数可以使用相同的 O 表示法表示.这里，O 表示函数的阶，它只提供了函数增长率的上限.

This means that, Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. Here, O means order of the function, and it only provides an upper bound on the growth rate of the function.

现在让我们看看Big O的规则:

Now let us look at the rules of Big O:

• 如果 f(x) 是几项的总和，如果存在最大的一项增长率，可以保留，其他都省略
• 如果 f(x) 是几个因子的乘积，则任何常数(不依赖于 x) 的乘积可以省略.

示例:

f(x) = 6x^4 − 2x^3 + 5

f(x) = 6x^4 − 2x^3 + 5

使用第一条规则我们可以把它写成，f(x) = 6x^4

Using the 1st rule we can write it as, f(x) = 6x^4

使用第二条规则，它会给我们，O(x^4)

Using the 2nd rule it will give us, O(x^4)

最坏情况分析给出了最大的基本操作数必须在算法执行期间执行.它假设输入处于可能的最坏状态，并且必须完成最大工作做正确的事情.

Worst case analysis gives the maximum number of basic operations that have to be performed during execution of the algorithm. It assumes that the input is in the worst possible state and maximum work has to be done to put things right.

例如，对于旨在按升序对数组进行排序的排序算法，最坏的情况发生在输入数组按降序排列时.在这种情况下，必须执行最大数量的基本操作(比较和赋值)才能按升序设置数组.

For example, for a sorting algorithm which aims to sort an array in ascending order, the worst case occurs when the input array is in descending order. In this case maximum number of basic operations (comparisons and assignments) have to be done to set the array in ascending order.

这取决于很多事情，例如:

It depends on a lot of things like:

• CPU(时间)使用率
• 内存使用
• 磁盘使用情况
• 网络使用情况

Big-O 常用于对衡量算法最坏情况行为的函数进行陈述，但 big-O 表示法并不暗示任何此类行为.

Big-O is often used to make statements about functions that measure the worst case behavior of an algorithm, but big-O notation doesn’t imply anything of the sort.

这里的重点是我们谈论的是增长，而不是运营数量.但是，对于算法，我们确实会讨论与输入大小相关的操作数量.

The important point here is we're talking in terms of growth, not number of operations. However, with algorithms we do talk about the number of operations relative to the input size.

Big-O 用于对函数进行声明.这些功能可以测量时间或空间或缓存未命中或岛上的兔子或任何东西或什么都没有.Big-O 表示法不在乎.

Big-O is used for making statements about functions. The functions can measure time or space or cache misses or rabbits on an island or anything or nothing. Big-O notation doesn’t care.

事实上，当用于算法时，big-O 几乎从来都不是关于时间的.这是关于原始操作.

In fact, when used for algorithms, big-O is almost never about time. It is about primitive operations.

当有人说 MergeSort 的时间复杂度是 O(nlogn) 时，他们通常是指 MergeSort 进行的比较次数是 O(nlogn).这本身并不能告诉我们任何特定 MergeSort 的时间复杂度可能是多少，因为这取决于进行比较所需的时间.换句话说，O(nlogn) 将比较称为原始操作.

When someone says that the time complexity of MergeSort is O(nlogn), they usually mean that the number of comparisons that MergeSort makes is O(nlogn). That in itself doesn’t tell us what the time complexity of any particular MergeSort might be because that would depend how much time it takes to make a comparison. In other words, the O(nlogn) refers to comparisons as the primitive operation.

这里的重点是，当 big-O 应用于算法时，总会有一个底层的计算模型.声称 MergeSort 的时间复杂度为 O(nlogn) 的说法隐含地引用了一个计算模型，其中比较需要恒定时间而其他一切都是免费的.

The important point here is that when big-O is applied to algorithms, there is always an underlying model of computation. The claim that the time complexity of MergeSort is O(nlogn), is implicitly referencing an model of computation where a comparison takes constant time and everything else is free.

示例 -

如果我们对长度为 kk 个字节的字符串进行排序，我们可能会将读取一个字节"作为一种原始操作，该操作需要恒定的时间，而其他一切都是空闲的.

If we are sorting strings that are kk bytes long, we might take "read a byte" as a primitive operation that takes constant time with everything else being free.

在这个模型中，MergeSort 进行 O(nlogn) 次字符串比较，每一次进行 O(k) 字节比较，因此时间复杂度为 O(k⋅nlogn).RadixSort 的一种常见实现是让 k 次遍历 n 个字符串，每次读取一个字节，因此时间复杂度为 O(nk).

In this model, MergeSort makes O(nlogn) string comparisons each of which makes O(k) byte comparisons, so the time complexity is O(k⋅nlogn). One common implementation of RadixSort will make k passes over the n strings with each pass reading one byte, and so has time complexity O(nk).

这篇关于为什么 big-Oh 并不总是算法的最坏情况分析?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！