上限、下限
证明算法的上限或下限意味着什么？
What does it mean to prove an upper bound or lower bound to an algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
证明算法的上限或下限意味着什么？
What does it mean to prove an upper bound or lower bound to an algorithm?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（3）
证明上限意味着您已经证明算法将使用不超过资源的某个限制。
证明下限意味着您已经证明该算法将使用不少于资源的某个限制。
在这种情况下，“资源”可以是时间、内存、带宽或其他东西。
Proving an upper bound means you have proven that the algorithm will use no more than some limit on a resource.
Proving a lower bound means you have proven that the algorithm will use no less than some limit on a resource.
"Resource" in this context could be time, memory, bandwidth, or something else.
上限和下限与算法的最小和最大“复杂性”有关（我谨慎地使用这个词，因为它在复杂性分析中具有非常具体的含义）。
以我们的老朋友冒泡排序为例。在所有数据都已排序的理想情况下，所花费的时间为 f(n)，该函数取决于 n（列表中的项目数）。这是因为您只需对数据集进行一次传递（零交换）即可确保列表已排序。
在特别糟糕的情况下，数据按照与您想要的顺序相反的顺序排序，所花费的时间将变为 f(n2)。这是因为每一遍都会将一个元素移动到正确的位置，并且您需要
n遍才能完成所有元素。在这种情况下，即使 big-O 复杂度保持不变，上限和下限也不同。
顺便说一句，冒泡排序饱受诟病（通常有充分的理由），但在某些情况下它是有意义的。实际上，我在一个应用程序中使用它，其中大部分数据已经排序，并且一次只会将一两个项目添加到列表末尾。对于添加一项，并使用反向冒泡排序，您可以保证新列表将一次性排序。这说明了下界概念。
事实上，您可以对冒泡排序进行优化，将下限设置为 f(1)，只需提供指示列表是否已排序的额外数据即可。您可以在排序后设置此项，并在将项目添加到末尾时清除它。
Upper and lower bounds have to do with the minimum and maximum "complexity" of an algorithm (I use that word advisedly since it has a very specific meaning in complexity analysis).
Take, for example, our old friend, the bubble sort. In an ideal case where all the data are already sorted, the time taken is f(n), a function dependent on
n, the number of items in the list. That's because you only have to make one pass of the data set (with zero swaps) to ensure your list is sorted.In a particularly bad case where the data are sorted in the opposite to the order you want, the time taken becomes f(n2). This is because each pass moves one element to the right position and you need
npasses to do all elements.In that case, the upper and lower bounds are different, even though the big-O complexity remains the same.
As an aside, the bubble sort is much maligned (usually for good reasons) but it can make sense in certain circumstances. I actually use it in an application where the bulk of the data are already sorted and only one or two items tend to be added at a time to the end of the list. For adding one item, and with a reverse-directional bubble sort, you can guarantee the new list will be sorted in one pass. That illustrates the lower bound concept.
In fact, you could make an optimization of the bubble sort that sets the lower bound to f(1), simply by providing an extra datum which indicates whether the list is sorted. You would set this after sorting and clear it when adding an item to the end.
无论界限是什么（上限或下限），我们总是谈论我们可以考虑的最坏情况输入。例如，在排序中，我们假设最坏的情况是未排序的输入列表。
我的理解是问题有一个下限。例如，我们说基于比较的排序的下界是\Omega(n log n)；我们不对我们使用的特定的基于比较的排序算法做出任何假设。无论哪种算法（归并排序、快速排序等），我们都不能比 \Omega(n log n) 的界限做得更好。下界直观地告诉我们特定问题的难度。
当我们谈论特定的算法时，我们谈论的是上限。例如，我们说冒泡排序的上界是O(n^2)，归并排序的上界是O(n log n)。直观上，上限告诉我们特定算法在解决问题方面有多好。
Whatever the bound (upper or lower), we are always talking about the worst-case input that we can consider. For example, in sorting, we assume that the worst-case is an unsorted input list.
My understanding is that problems have a lower bound. For example, we say that the lower bound of comparison-based sorting is \Omega(n log n); we are making no assumptions about what particular comparison-based sorting algorithm we use. Whatever the algorithm (merge sort, quick sort, etc), we cannot do better than this bound of \Omega(n log n). Lower bounds tell us, intuitively, how hard a particular problem is.
When we talk about a specific algorithm, then we talk about upper bounds. For example, we say that the upper bound of bubble sort is O(n^2) and the upper bound of merge sort is O(n log n). Upper bounds, intuitively, tell us how good a particular algorithm is at solving the problem.