更改

In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms – the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the length of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same length may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest.  When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst case inputs to the algorithm.

In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms – the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the length of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same length may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest.  When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst case inputs to the algorithm.

在'''<font color="#ff8000">计算机科学 Computer Science</font>'''中，算法分析是查找算法计算复杂性的过程——算法执行时间、所需存储空间或其他资源的数量。通常，这是一个确定函数，该函数将一个算法的输入长度与所需的迭代步数（时间复杂度）或使用的存储大小（空间复杂度）相关联。当某个算法的算法复杂性函数取值很小，或者其函数值大小与输入大小的增长相比增长缓慢时，我们认为该算法是有效的。相同长度的不同输入可能导致算法表现出不同的效果，因此对算法运行的最佳、最差和平均情况的描述都可能具有一定的实际意义。但是当没有特殊说明，算法性能描述函数通常反映的是一个算法复杂性上界，由算法表现的最差情况的输入确定。

在'''<font color="#ff8000">计算机科学 Computer Science</font>'''中，算法分析是计算查找算法复杂性的过程——包括算法执行时间、所需存储空间或其他资源的数量。通常这是一个确定函数，该函数将一个算法的输入长度与所需的迭代步数（时间复杂度）或使用的存储大小（空间复杂度）相关联。当某个算法其算法复杂性函数的取值很小，或者其函数值大小的增长速度与算法输入大小的相比更加缓慢时，我们认为该算法是有效的。相同长度的不同输入可能导致算法表现出不同的效果，因此对算法运行的最佳、最差和平均情况的描述都可能具有一定的实际意义。但是当没有特殊说明时，算法性能描述函数通常反映的是算法复杂性一种上界，由算法表现最差情况的输入来确定。

The term "analysis of algorithms" was coined by Donald Knuth. Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable directions of search for efficient algorithms.

The term "analysis of algorithms" was coined by Donald Knuth. Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable directions of search for efficient algorithms.

“算法分析”这个术语是由 Donald Knuth 提出的。算法分析是广义计算复杂性理论的重要组成部分，它为任何解决给定计算问题的任何算法所需的资源提供理论估计。这些估计为有效算法的合理性评价提供了思路。

“算法分析”这个术语是由 Donald Knuth 提出的。算法分析是广义计算复杂性理论的重要组成部分，它为任何解决给定计算问题的算法所需的资源提供理论估计。这些估计为有效算法的合理性评价提供了思路。

In theoretical analysis of algorithms it is common to estimate their complexity in the asymptotic sense, i.e., to estimate the complexity function for arbitrarily large input. Big O notation, Big-omega notation and Big-theta notation are used to this end. For instance, binary search is said to run in a number of steps proportional to the logarithm of the length of the sorted list being searched, or in O(log(n)), colloquially "in logarithmic time". Usually asymptotic estimates are used because different implementations of the same algorithm may differ in efficiency. However the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor  called '''<font color="#32CD32">a hidden constant</font>'''.

In theoretical analysis of algorithms it is common to estimate their complexity in the asymptotic sense, i.e., to estimate the complexity function for arbitrarily large input. Big O notation, Big-omega notation and Big-theta notation are used to this end. For instance, binary search is said to run in a number of steps proportional to the logarithm of the length of the sorted list being searched, or in O(log(n)), colloquially "in logarithmic time". Usually asymptotic estimates are used because different implementations of the same algorithm may differ in efficiency. However the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor  called '''<font color="#32CD32">a hidden constant</font>'''.

在算法的理论分析中，通常是在渐近意义上估计它们的复杂性，即对任意大输入的复杂度函数进行估计。为了达到这个目的，我们使用到了大O符号、大Ω符号和大θ符号。例如，二进制搜索被称为以“与被搜索的排序列表长度的对数成正比”的若干步长运行，或者以O(log(n))，通俗地说是“以对数时间”运行。通常使用渐近估计，因为同一算法的不同实现的算法效率表现会有所不同。然而，给定算法的任何两个“合理”实现的效率，是由一个称为'''<font color="#32CD32">隐常数</font>'''的常数乘法因子相关联的。

在算法的理论分析中，通常是在渐近意义上估计它们的复杂性，即对任意大输入的复杂度函数进行估计。为了达到这个目的，我们使用到了大O符号、大Ω符号和大θ符号。例如，二进制搜索被称为以与“被搜索的排序列表长度的对数成正比”的若干步长来运行，或者用O(log(n))表示，通俗地说就是“以对数时间”运行。之所以我们通常使用渐近估计，是因为同一算法的不同实现的算法效率表现会有所不同。然而，给定算法的任何两个“合理”实现的效率，是由一个称为'''<font color="#32CD32">隐常数</font>'''的常数乘法因子相关联的。

Exact (not asymptotic) measures of efficiency can sometimes be computed but they usually require certain assumptions concerning the particular implementation of the algorithm, called [[model of computation]]. A model of computation may be defined in terms of an [[abstract machine|abstract computer]], e.g., [[Turing machine]], and/or by postulating that certain operations are executed in unit time.

Exact (not asymptotic) measures of efficiency can sometimes be computed but they usually require certain assumptions concerning the particular implementation of the algorithm, called [[model of computation]]. A model of computation may be defined in terms of an [[abstract machine|abstract computer]], e.g., [[Turing machine]], and/or by postulating that certain operations are executed in unit time.

Exact (not asymptotic) measures of efficiency can sometimes be computed but they usually require certain assumptions concerning the particular implementation of the algorithm, called model of computation. A model of computation may be defined in terms of an abstract computer, e.g., Turing machine, and/or by postulating that certain operations are executed in unit time.

'''<font color="#32CD32">Exact (not asymptotic) measures of efficiency can sometimes be computed but they usually require certain assumptions concerning the particular implementation of the algorithm, called model of computation. A model of computation may be defined in terms of an abstract computer, e.g., Turing machine, and/or by postulating that certain operations are executed in unit time.</font>'''

精确（而非渐近）的效率措施有时可以计算，但他们通常需要一定的假设关于特定的实施算法，称为计算模型。一个计算模型可以用抽象计算机来定义，例如图灵机，和 / 或通过假设某些操作在单位时间内执行。

'''<font color="#32CD32">算法效率的精确（这里就不是渐近了）度量有时是可以计算的，但它们通常需要一定的关于算法特定实现的假设，这种算法被称为计算模型。一个计算模型可以用抽象计算机来定义，例如图灵机，和 / 或通过假设某些操作在单位时间内执行。</font>'''

For example, if the sorted list to which we apply binary search has ''n'' elements, and we can guarantee that each lookup of an element in the list can be done in unit time, then at most log₂ ''n'' + 1 time units are needed to return an answer.

For example, if the sorted list to which we apply binary search has ''n'' elements, and we can guarantee that each lookup of an element in the list can be done in unit time, then at most log₂ ''n'' + 1 time units are needed to return an answer.

For example, if the sorted list to which we apply binary search has n elements, and we can guarantee that each lookup of an element in the list can be done in unit time, then at most log₂ n + 1 time units are needed to return an answer.

For example, if the sorted list to which we apply binary search has n elements, and we can guarantee that each lookup of an element in the list can be done in unit time, then at most log₂ n + 1 time units are needed to return an answer.

例如，如果我们应用二进制搜索的排序列表有 n 个元素，并且我们可以保证列表中每个元素的查找都可以在单位时间内完成，那么最多需要 log 子2 / sub n + 1时间单位来返回一个答案。

例如，如果我们应用二分法搜索的待排序列表有 n 个元素，并且我们可以保证列表中每个元素的查找都可以在单位时间内完成，那么最多需要 log₂ ''n'' + 1 的时间就可以得到返回值结果。

<!-- Exact measures of efficiency are useful to the people who actually implement and use algorithms, because they are more precise and thus enable them to know how much time they can expect to spend in execution. To some people (e.g. game programmers), a hidden constant can make all the difference between success and failure.-->

<!-- Exact measures of efficiency are useful to the people who actually implement and use algorithms, because they are more precise and thus enable them to know how much time they can expect to spend in execution. To some people (e.g. game programmers), a hidden constant can make all the difference between success and failure.-->

<!-- Exact measures of efficiency are useful to the people who actually implement and use algorithms, because they are more precise and thus enable them to know how much time they can expect to spend in execution. To some people (e.g. game programmers), a hidden constant can make all the difference between success and failure.-->

<!-- Exact measures of efficiency are useful to the people who actually implement and use algorithms, because they are more precise and thus enable them to know how much time they can expect to spend in execution. To some people (e.g. game programmers), a hidden constant can make all the difference between success and failure.-->

<！ ——对于实际实现和使用算法的人来说，精确的效率测量是有用的，因为算法更加精确，因此能够让他们知道自己在执行过程中预计会花费多少时间。对某些人来说(例如:。一个隐藏的常数可以决定成功和失败。——

<!-- 对于真实实现和使用算法的人来说，精确的效率测量是有用的，因为算法更加精确能够让他们知道自己在执行过程中预计会花费多少时间。对某些人来说（如游戏开发者们），事情的成败往往可能是一个隐藏的常数。-->

Time efficiency estimates depend on what we define to be a step. For the analysis to correspond usefully to the actual execution time, the time required to perform a step must be guaranteed to be bounded above by a constant. One must be careful here; for instance, some analyses count an addition of two numbers as one step. This assumption may not be warranted in certain contexts. For example, if the numbers involved in a computation may be arbitrarily large, the time required by a single addition can no longer be assumed to be constant.

Time efficiency estimates depend on what we define to be a step. For the analysis to correspond usefully to the actual execution time, the time required to perform a step must be guaranteed to be bounded above by a constant. One must be careful here; for instance, some analyses count an addition of two numbers as one step. This assumption may not be warranted in certain contexts. For example, if the numbers involved in a computation may be arbitrarily large, the time required by a single addition can no longer be assumed to be constant.

* the '''uniform cost model''', also called '''uniform-cost measurement''' (and similar variations), assigns a constant cost to every machine operation, regardless of the size of the numbers involved

* the '''uniform cost model''', also called '''uniform-cost measurement''' (and similar variations), assigns a constant cost to every machine operation, regardless of the size of the numbers involved

* the '''logarithmic cost model''', also called '''logarithmic-cost measurement''' (and similar variations), assigns a cost to every machine operation proportional to the number of bits involved

* the '''logarithmic cost model''', also called '''logarithmic-cost measurement''' (and similar variations), assigns a cost to every machine operation proportional to the number of bits involved

A key point which is often overlooked is that published lower bounds for problems are often given for a model of computation that is more restricted than the set of operations that you could use in practice and therefore there are algorithms that are faster than what would naively be thought possible.

A key point which is often overlooked is that published lower bounds for problems are often given for a model of computation that is more restricted than the set of operations that you could use in practice and therefore there are algorithms that are faster than what would naively be thought possible.

== 运行时分析 Run-time analysis ==

== 运行时分析 Run-time analysis ==

Run-time analysis is a theoretical classification that estimates and anticipates the increase in running time (or run-time) of an algorithm as its input size (usually denoted as n) increases.  Run-time efficiency is a topic of great interest in computer science:  A program can take seconds, hours, or even years to finish executing, depending on which algorithm it implements. While software profiling techniques can be used to measure an algorithm's run-time in practice, they cannot provide timing data for all infinitely many possible inputs; the latter can only be achieved by the theoretical methods of run-time analysis.

Run-time analysis is a theoretical classification that estimates and anticipates the increase in running time (or run-time) of an algorithm as its input size (usually denoted as n) increases.  Run-time efficiency is a topic of great interest in computer science:  A program can take seconds, hours, or even years to finish executing, depending on which algorithm it implements. While software profiling techniques can be used to measure an algorithm's run-time in practice, they cannot provide timing data for all infinitely many possible inputs; the latter can only be achieved by the theoretical methods of run-time analysis.

运行时分析是一种理论分类，它随着算法输入大小(通常表示为 n)的增加而估计和预期运行时间(或运行时间)的增加。运行时效率是计算机科学中非常感兴趣的话题: 一个程序可能需要几秒钟、几小时甚至几年才能完成执行，这取决于它实现的算法。虽然软件分析技术可用于在实践中测量算法的运行时间，但它们不能为所有无限多可能的输入提供计时数据; 后者只能通过运行时间分析的理论方法来实现。

运行时分析是一种理论分类，它得出的算法预期运行时间（或运行时间）是随着算法输入大小（通常表示为 n）的增加而增加的。运行时效率是计算机科学中一个热门话题: 一个程序究竟是需要几秒钟还是几小时甚至几年才能完成执行，这取决于它具体实现的方法。虽然软件分析技术可用于在实践中测量算法的运行时间，但它们不能为所有无限多可能的输入提供计时数据; 后者只能通过运行时间分析的理论方法来实现。

Take as an example a program that looks up a specific entry in a sorted list of size n.  Suppose this program were implemented on Computer A, a state-of-the-art machine, using a linear search algorithm, and on Computer B, a much slower machine, using a binary search algorithm.  Benchmark testing on the two computers running their respective programs might look something like the following:

Take as an example a program that looks up a specific entry in a sorted list of size n.  Suppose this program were implemented on Computer A, a state-of-the-art machine, using a linear search algorithm, and on Computer B, a much slower machine, using a binary search algorithm.  Benchmark testing on the two computers running their respective programs might look something like the following:

举个例子，一个程序在一个大小的排序列表中查找一个特定的条目。假设这个程序是在 a 计算机上实现的，a 计算机是最先进的机器，使用线性搜索算法，b 计算机使用二进制搜索算法，b 计算机速度要慢得多。在运行各自程序的两台计算机上进行的基准测试可能看起来如下所示:

举个例子，一个程序在一个大小为n的排序列表中查找一个特定的条目。假设这个程序是在A计算机上实现的，A计算机是最先进的机器，使用线性搜索算法，而B计算机使用二分法进行搜索，但是B计算机本身的运行速度要慢得多。两台计算机分别运行该程序的基准测试结果如下所示:

Based on these metrics, it would be easy to jump to the conclusion that Computer A is running an algorithm that is far superior in efficiency to that of Computer B.  However, if the size of the input-list is increased to a sufficient number, that conclusion is dramatically demonstrated to be in error:

Based on these metrics, it would be easy to jump to the conclusion that Computer A is running an algorithm that is far superior in efficiency to that of Computer B.  However, if the size of the input-list is increased to a sufficient number, that conclusion is dramatically demonstrated to be in error:

Computer A, running the linear search program, exhibits a linear growth rate.  The program's run-time is directly proportional to its input size.  Doubling the input size doubles the run time, quadrupling the input size quadruples the run-time, and so forth.  On the other hand, Computer B, running the binary search program, exhibits a logarithmic growth rate.  Quadrupling the input size only increases the run time by a constant amount (in this example, 50,000 ns).  Even though Computer A is ostensibly a faster machine, Computer B will inevitably surpass Computer A in run-time because it's running an algorithm with a much slower growth rate.

Computer A, running the linear search program, exhibits a linear growth rate.  The program's run-time is directly proportional to its input size.  Doubling the input size doubles the run time, quadrupling the input size quadruples the run-time, and so forth.  On the other hand, Computer B, running the binary search program, exhibits a logarithmic growth rate.  Quadrupling the input size only increases the run time by a constant amount (in this example, 50,000 ns).  Even though Computer A is ostensibly a faster machine, Computer B will inevitably surpass Computer A in run-time because it's running an algorithm with a much slower growth rate.

运行线性搜索程序的计算机 a 呈现线性增长率。程序的运行时间与其输入大小成正比。将输入大小增加一倍将运行时间增加一倍，将输入大小增加四倍将运行时间增加四倍，等等。另一方面，运行二进制搜索程序的计算机 b 呈现出对数增长率。将输入大小翻两番只会使运行时增加一个常量(在本例中为50,000 ns)。尽管计算机 a 表面上是一台速度更快的机器，但计算机 b 在运行时将不可避免地超过计算机 a，因为它运行的算法增长速度要慢得多。

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

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

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