更改

运行线性搜索程序的计算机A的效率呈现线性增长，即程序的运行时间与其输入大小成正比，也就是说将输入大小增加一倍时运行时间也将增加一倍，将输入大小增加四倍则运行时间也会增加四倍等等。另一方面，运行二分法搜索程序的计算机B的效率呈现出对数增长趋势，将输入大小变成原来的两倍只会使运行时增加一个常量（在本例中为50,000 ns）。尽管从表面上看计算机A是一台速度更快的机器，但计算机B在运行时势必会地超过计算机A，因为它运行的算法增长速度要慢得多。

运行线性搜索程序的计算机A的效率呈现线性增长，即程序的运行时间与其输入大小成正比，也就是说将输入大小增加一倍时运行时间也将增加一倍，将输入大小增加四倍则运行时间也会增加四倍等等。另一方面，运行二分法搜索程序的计算机B的效率呈现出对数增长趋势，将输入大小变成原来的两倍只会使运行时增加一个常量（在本例中为50,000 ns）。尽管从表面上看计算机A是一台速度更快的机器，但计算机B在运行时势必会地超过计算机A，因为它运行的算法增长速度要慢得多。

===生长规律 Orders of growth===

===生长规律===

{{main|Big O notation}}

非正式地，一个算法可以说表现出一个数学函数级的增长率，如果超过一定的输入大小''n''，函数乘以一个正常数为该算法的运行时间提供了一个上限或极限。换言之，对于给定的输入大小''n''大于某个''n''₀和常数''c''，该算法的运行时间永远不会大于。这个概念经常使用大写字母''O''符号表示。例如，由于插入排序的运行时随着其输入大小的增加而二次增长，因此插入排序的时间复杂度可以表示为''O''(''n''²)。

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

对于给定的算法，大O表示法是表达算法最坏情况的一种简便方法，尽管它也可以用来表示平均情况-例如，快速排序的最差表现是''O''(''n''²) ，但是平均情况下其运行时是{{math|''O''(''n'' log ''n'')}}。

非正式地，一个算法可以说表现出一个数学函数级的增长率，如果超过一定的输入大小 n，函数乘以一个正常数为该算法的运行时间提供了一个上限或极限。换言之，对于给定的输入大小n大于某个n0和常数c，该算法的运行时间永远不会大于。这个概念经常用大O符号表示。这个概念经常使用大 o 符号表示。例如，由于插入排序的运行时随着其输入大小的增加而二次增长，因此插入排序的时间复杂度可以表示为O(n²)。

<br>

 

 

 

 

 

===经验增长规律 Empirical orders of growth===

===经验增长规律 Empirical orders of growth===