463
个编辑
更改
→生长规律 Orders of growth
Informally, an algorithm can be said to exhibit a growth rate on the order of a mathematical function if beyond a certain input size n, the function times a positive constant provides an upper bound or limit for the run-time of that algorithm. In other words, for a given input size n greater than some n<sub>0</sub> and a constant c, the running time of that algorithm will never be larger than . This concept is frequently expressed using Big O notation. For example, since the run-time of insertion sort grows quadratically as its input size increases, insertion sort can be said to be of order O(n<sup>2</sup>).
Informally, an algorithm can be said to exhibit a growth rate on the order of a mathematical function if beyond a certain input size n, the function times a positive constant provides an upper bound or limit for the run-time of that algorithm. In other words, for a given input size n greater than some n<sub>0</sub> and a constant c, the running time of that algorithm will never be larger than . This concept is frequently expressed using Big O notation. For example, since the run-time of insertion sort grows quadratically as its input size increases, insertion sort can be said to be of order O(n<sup>2</sup>).
非正式地，一个算法可以说表现出一个数学函数级的增长率，如果超过一定的输入大小 n，函数乘以一个正常数为该算法的运行时间提供了一个上限或极限。换句话说，对于给定的输入大小 n 大于 n 个子0 / 子和一个常数 c，该算法的运行时间永远不会大于。这个概念经常使用大 o 符号表示。例如，由于插入排序的运行时随着其输入大小的增加而二次增长，因此插入排序可以说是 o (n sup 2 / sup)的顺序。
非正式地，一个算法可以说表现出一个数学函数级的增长率，如果超过一定的输入大小 n，函数乘以一个正常数为该算法的运行时间提供了一个上限或极限。换言之，对于给定的输入大小n大于某个n0和常数c，该算法的运行时间永远不会大于。这个概念经常用大O符号表示。这个概念经常使用大 o 符号表示。例如，由于插入排序的运行时随着其输入大小的增加而二次增长，因此插入排序的时间复杂度可以表示为O(n<sup>2</sup>)。
Big O notation is a convenient way to express the worst-case scenario for a given algorithm, although it can also be used to express the average-case — for example, the worst-case scenario for quicksort is O(n<sup>2</sup>), but the average-case run-time is .
Big O notation is a convenient way to express the worst-case scenario for a given algorithm, although it can also be used to express the average-case — for example, the worst-case scenario for quicksort is O(n<sup>2</sup>), but the average-case run-time is .
对于给定的算法，大O表示法是表达算法最坏情况的一种简便方法，尽管它也可以用来表示平均情况-例如，快速排序的最差表现是 O(n<sup>2</sup>) ，但是平均情况下其运行时是{{math|''O''(''n'' log ''n'')}}。
===经验增长规律 Empirical orders of growth===
===经验增长规律 Empirical orders of growth===