Big O表示法的复杂度顺序是什么？ [英] what is order of complexity in Big O notation?

问题描述

问题

您好，我想了解以大O表示法表示的复杂程度是多少。我已经阅读了许多文章，甚至在这里没有关于Big O的有用描述的情况下，也找不到能确切解释复杂性顺序的东西。

Hi I am trying to understand what order of complexity in terms of Big O notation is. I have read many articles and am yet to find anything explaining exactly 'order of complexity', even on the useful descriptions of Big O on here.

我要做什么我已经了解了大O

我已经了解的部分。关于Big O表示法是，我们正在根据输入大小n的增长来衡量算法的时间和空间复杂度。我也了解某些排序方法对于大O而言具有最佳，最坏和平均的情况，例如O（n），O（n ^ 2）等，而n是输入大小（要排序的元素数）。

The part which I already understand. about Big O notation is that we are measuring the time and space complexity of an algorithm in terms of the growth of input size n. I also understand that certain sorting methods have best, worst and average scenarios for Big O such as O(n) ,O(n^2) etc and the n is input size (number of elements to be sorted).

任何简单的定义或示例，将不胜感激，谢谢。

Any simple definitions or examples would be greatly appreciated thanks.

推荐答案

大O在于找到某些函数增长的上限。请参阅Wikipedia上的正式定义 http://en.wikipedia.org/wiki/Big_O_notation

Big O is about finding an upper limit for the growth of some function. See the formal definition on Wikipedia http://en.wikipedia.org/wiki/Big_O_notation

因此，如果您有一种算法可以对大小为 n 的数组进行排序，并且只需要恒定量的额外空间，它需要（例如） 2n²+ n 个步骤来完成，那么您会说它的空间复杂度是 O（n）或 O（1）（取决于是否计算输入数组的大小），其时间复杂度为 O（ n²）。

So if you've got an algorithm that sorts an array of size n and it requires only a constant amount of extra space and it takes (for example) 2 n² + n steps to complete, then you would say it's space complexity is O(n) or O(1) (depending on wether you count the size of the input array or not) and it's time complexity is O(n²).

仅知道那些 O 个数字，您可以大致确定多少从 n 到 n + 100 或 2 n 或您感兴趣的任何内容。这就是算法扩展的程度。

Knowing only those O numbers, you could roughly determine how much more space and time is needed to go from n to n + 100 or 2 n or whatever you are interested in. That is how well an algorithm "scales".

更新

大O和复杂性实际上只是同一件事的两个术语。您可以说线性复杂度代替 O（n），二次复杂度代替 O（n²），等等...

Big O and complexity are really just two terms for the same thing. You can say "linear complexity" instead of O(n), quadratic complexity instead of O(n²), etc...

这篇关于Big O表示法的复杂度顺序是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！