更改

For looking up a given entry in a given ordered list, both the binary and the linear search algorithm (which ignores ordering) can be used. The analysis of the former and the latter algorithm shows that it takes at most log₂(''n'') and ''n'' check steps, respectively, for a list of length n. In the depicted example list of length 33, searching for "Morin, Arthur" takes 5 and 28 steps with binary and linear search, respectively.

For looking up a given entry in a given ordered list, both the binary and the linear search algorithm (which ignores ordering) can be used. The analysis of the former and the latter algorithm shows that it takes at most log₂(''n'') and ''n'' check steps, respectively, for a list of length n. In the depicted example list of length 33, searching for "Morin, Arthur" takes 5 and 28 steps with binary and linear search, respectively.

二进制和线性搜索算法(忽略排序)可以使用。对前者和后者的分析表明，对于一个长度 n 的列表，分别采用最多的 log 子2 / sub (n)和 n 个检查步骤。 在长度为33的示例列表中，搜索“ Morin，Arthur”需要5步和28步，分别使用二进制(如图所示)和线性(如图所示)搜索

二进制和线性搜索算法（忽略排序）可以使用。对前者和后者的分析表明，对于一个长度 n 的列表，分别采用最多的 log 子2 / sub (n)和 n 个检查步骤。 在长度为33的示例列表中，搜索“ Morin，Arthur”需要5步和28步，分别使用二进制(如图所示)和线性(如图所示)搜索

[[File:comparison_computational_complexity.svg|thumb|Graphs of functions commonly used in the analysis of algorithms, showing the number of operations ''N'' versus input size ''n'' for each function]]

[[File:comparison_computational_complexity.svg|thumb|Graphs of functions commonly used in the analysis of algorithms, showing the number of operations ''N'' versus input size ''n'' for each function]]

Graphs of functions commonly used in the analysis of algorithms, showing the number of operations N versus input size n for each function

Graphs of functions commonly used in the analysis of algorithms, showing the number of operations N versus input size n for each function

在算法分析中常用的函数图，显示每个函数的操作数 N 与输入大小 n 的对应关系

在算法分析中常用函数图，表示每个函数的操作数 N 与输入大小 n 的对应关系

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 [[computation|execute them]]. Usually, this involves determining a [[Function (mathematics)|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 [[computation|execute them]]. Usually, this involves determining a [[Function (mathematics)|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.

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.

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 analysis|asymptotic]] estimates are used because different [[implementation]]s 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 a ''hidden constant''.

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 analysis|asymptotic]] estimates are used because different [[implementation]]s 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 a ''hidden constant''.

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 a hidden constant.

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 符号、大 -omega 符号和大 -theta 符号被用于此目的。例如，二进制搜索被称为以与被搜索的排序列表长度的对数成正比的若干步长运行，或者以 o (log (n))通俗地称为“对数时间”。通常使用渐近估计，因为同一算法的不同实现可能在效率上有所不同。然而，给定算法的任何两个“合理”实现的效率是由一个称为隐常数的常数乘法因子相关联的。

在算法的理论分析中，通常是在渐近意义上估计它们的复杂性，即对任意大输入的复杂度函数进行估计。为了达到这个目的，我们使用到了大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 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.

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

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

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.