1,568
个编辑
更改
跳到导航
跳到搜索
Moved page from wikipedia:en:Analysis of algorithms (history)
此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。
{{more footnotes|date=March 2010}}
[[File:Binary search vs Linear search example svg.svg|thumb|For looking up a given entry in a given ordered list, both the [[binary search algorithm|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<sub>2</sub>(''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 (shown in {{color|#008080|cyan}}) and linear ({{color|#800080|magenta}}) search, respectively.]]
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<sub>2</sub>(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 (shown in ) and linear () search, respectively.]]
二进制和线性搜索算法(忽略排序)可以使用。对前者和后者的分析表明，对于一个长度 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]]
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 的对应关系
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.
在计算机科学中，算法分析是查找算法计算复杂性的过程——执行它们所需的时间、存储空间或其他资源的数量。通常，这涉及到确定一个函数，该函数将算法的输入长度与它所采取的步骤数(其时间复杂度)或它所使用的存储位置数(其空间复杂度)联系起来。当这个函数的值很小，或者与输入大小的增长相比增长缓慢时，一个算法被认为是有效的。相同长度的不同输入可能导致算法具有不同的行为，因此最佳、最差和平均情况描述都可能具有实际意义。当没有另外指定时，描述算法性能的函数通常是一个上界，由算法的最坏情况输入确定。
The term "analysis of algorithms" was coined by [[Donald Knuth]].<ref>{{cite web|url=https://web.archive.org/web/20160828152021/http://www-cs-faculty.stanford.edu/~uno/news.html|title=Knuth: Recent News|date=28 August 2016|website=web.archive.org}}</ref> 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 [[Algorithmic efficiency|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 创造的。算法分析是更广泛的计算复杂性理论分析的重要组成部分，它为任何解决给定计算问题的算法所需的资源提供理论估计。这些估计为寻找有效算法的合理方向提供了洞察力。
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.
在算法的理论分析中，通常是在渐近意义上估计它们的复杂性，即对任意大的输入估计复杂性函数。大 o 符号、大 -omega 符号和大 -theta 符号被用于此目的。例如，二进制搜索被称为以与被搜索的排序列表长度的对数成正比的若干步长运行，或者以 o (log (n))通俗地称为“对数时间”。通常使用渐近估计，因为同一算法的不同实现可能在效率上有所不同。然而，给定算法的任何两个“合理”实现的效率是由一个称为隐常数的常数乘法因子相关联的。
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.
精确(而非渐近)的效率措施有时可以计算，但他们通常需要一定的假设关于特定的实施算法，称为计算模型。一个计算模型可以用抽象计算机来定义，例如图灵机，和 / 或通过假设某些操作在单位时间内执行。
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<sub>2</sub> ''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<sub>2</sub> n + 1 time units are needed to return an answer.
例如，如果我们应用二进制搜索的排序列表有 n 个元素，并且我们可以保证列表中每个元素的查找都可以在单位时间内完成，那么最多需要 log 子2 / sub 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.-->
<！ ——对于实际实现和使用算法的人来说，精确的效率测量是有用的，因为算法更加精确，因此能够让他们知道自己在执行过程中预计会花费多少时间。对某些人来说(例如:。一个隐藏的常数可以决定成功和失败。——
== Cost models ==
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.
时间效率的估计取决于我们对步骤的定义。为了使分析有效地对应于实际执行时间，执行一个步骤所需的时间必须保证在一个常数之上。这里我们必须小心; 例如，有些分析把两个数字的相加计算为一个步骤。在某些情况下，这种假设可能是不正当的。例如，如果计算中涉及的数字可能是任意大的，那么单个加法所需的时间就不能再假定为常数。
Two cost models are generally used:<ref name="AhoHopcroft1974">{{cite book|author1=Alfred V. Aho|author2=John E. Hopcroft|author3=Jeffrey D. Ullman|title=The design and analysis of computer algorithms|url=https://archive.org/details/designanalysisof00ahoarich|url-access=registration|year=1974|publisher=Addison-Wesley Pub. Co.}}, section 1.3</ref><ref name="Hromkovič2004">{{cite book|author=Juraj Hromkovič|title=Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography|url=https://books.google.com/books?id=KpNet-n262QC&pg=PA177|year=2004|publisher=Springer|isbn=978-3-540-14015-3|pages=177–178}}</ref><ref name="Ausiello1999">{{cite book|author=Giorgio Ausiello|title=Complexity and approximation: combinatorial optimization problems and their approximability properties|url=https://books.google.com/books?id=Yxxw90d9AuMC&pg=PA3|year=1999|publisher=Springer|isbn=978-3-540-65431-5|pages=3–8}}</ref><ref name=Wegener20>{{Citation|last1=Wegener|first1=Ingo|title=Complexity theory: exploring the limits of efficient algorithms|publisher=[[Springer-Verlag]]|location=Berlin, New York|isbn=978-3-540-21045-0|year=2005|page=20|url=https://books.google.com/books?id=u7DZSDSUYlQC&pg=PA20}}</ref><ref name="Tarjan1983">{{cite book|author=[[Robert Endre Tarjan]]|title=Data structures and network algorithms|url=https://books.google.com/books?id=JiC7mIqg-X4C&pg=PA3|year=1983|publisher=SIAM|isbn=978-0-89871-187-5|pages=3–7}}</ref>
Two cost models are generally used:
通常使用两种成本模型:
* 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 latter is more cumbersome to use, so it's only employed when necessary, for example in the analysis of [[arbitrary-precision arithmetic]] algorithms, like those used in [[cryptography]].
The latter is more cumbersome to use, so it's only employed when necessary, for example in the analysis of arbitrary-precision arithmetic algorithms, like those used in cryptography.
后者使用起来比较麻烦，所以只有在必要的时候才会使用，例如在分析高精度计算算法时，就像那些在密码学中使用的算法。
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.<ref>[https://cstheory.stackexchange.com/q/608 Examples of the price of abstraction?], cstheory.stackexchange.com</ref>
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 is a theoretical classification that estimates and anticipates the increase in ''[[DTIME|running time]]'' (or run-time) of an [[algorithm]] as its ''[[Information|input size]]'' (usually denoted as ''n'') increases. Run-time efficiency is a topic of great interest in [[computer science]]: A [[Computer program|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)的增加而估计和预期运行时间(或运行时间)的增加。运行时效率是计算机科学中非常感兴趣的话题: 一个程序可能需要几秒钟、几小时甚至几年才能完成执行，这取决于它实现的算法。虽然软件分析技术可用于在实践中测量算法的运行时间，但它们不能为所有无限多可能的输入提供计时数据; 后者只能通过运行时间分析的理论方法来实现。
===Shortcomings of empirical metrics===
Since algorithms are [[platform-independent]] (i.e. a given algorithm can be implemented in an arbitrary [[programming language]] on an arbitrary [[computer]] running an arbitrary [[operating system]]), there are additional significant drawbacks to using an [[empirical]] approach to gauge the comparative performance of a given set of algorithms.
Since algorithms are platform-independent (i.e. a given algorithm can be implemented in an arbitrary programming language on an arbitrary computer running an arbitrary operating system), there are additional significant drawbacks to using an empirical approach to gauge the comparative performance of a given set of algorithms.
由于算法是独立于平台的(即。一个给定的算法可以在任意运行任意操作系统的计算机上用任意编程语言实现) ，使用经验方法来衡量一组给定算法的比较性能还有一个明显的缺点。
Take as an example a program that looks up a specific entry in a [[collation|sorted]] [[list (computing)|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 (computing)|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 计算机速度要慢得多。在运行各自程序的两台计算机上进行的基准测试可能看起来如下所示:
{| class="wikitable"
{| class="wikitable"
{ | class“ wikitable”
|-
|-
|-
! ''n'' (list size)
! n (list size)
!N (列表大小)
! Computer A run-time<br />(in [[nanosecond]]s)
! Computer A run-time<br />(in nanoseconds)
!运行时 br / (以纳秒为单位)
! Computer B run-time<br />(in [[nanosecond]]s)
! Computer B run-time<br />(in nanoseconds)
!计算机 b 运行时 br / (以纳秒为单位)
|-
|-
|-
| 16
| 16
| 16
| 8
| 8
| 8
| 100,000
| 100,000
| 100,000
|-
|-
|-
| 63
| 63
| 63
| 32
| 32
| 32
| 150,000
| 150,000
| 150,000
|-
|-
|-
| 250
| 250
| 250
| 125
| 125
| 125
| 200,000
| 200,000
| 200,000
|-
|-
|-
| 1,000
| 1,000
| 1,000
| 500
| 500
| 500
| 250,000
| 250,000
| 250,000
|}
|}
|}
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:
基于这些度量，我们很容易得出结论: a 计算机运行的算法在效率上远远优于 b 计算机。然而，如果输入列表的大小增加到一个足够大的数字，这个结论就会被戏剧性地证明是错误的:
{| class="wikitable"
{| class="wikitable"
{ | class“ wikitable”
|-
|-
|-
! ''n'' (list size)
! n (list size)
!N (列表大小)
! Computer A run-time<br />(in [[nanosecond]]s)
! Computer A run-time<br />(in nanoseconds)
!运行时 br / (以纳秒为单位)
! Computer B run-time<br />(in [[nanosecond]]s)
! Computer B run-time<br />(in nanoseconds)
!计算机 b 运行时 br / (以纳秒为单位)
|-
|-
|-
| 16
| 16
| 16
| 8
| 8
| 8
| 100,000
| 100,000
| 100,000
|-
|-
|-
| 63
| 63
| 63
| 32
| 32
| 32
| 150,000
| 150,000
| 150,000
|-
|-
|-
| 250
| 250
| 250
| 125
| 125
| 125
| 200,000
| 200,000
| 200,000
|-
|-
|-
| 1,000
| 1,000
| 1,000
| 500
| 500
| 500
| 250,000
| 250,000
| 250,000
|-
|-
|-
| ...
| ...
| ...
| ...
| ...
| ...
| ...
| ...
| ...
|-
|-
|-
| 1,000,000
| 1,000,000
| 1,000,000
| 500,000
| 500,000
| 500,000
| 500,000
| 500,000
| 500,000
|-
|-
|-
| 4,000,000
| 4,000,000
| 4,000,000
| 2,000,000
| 2,000,000
| 2,000,000
| 550,000
| 550,000
| 550,000
|-
|-
|-
| 16,000,000
| 16,000,000
| 16,000,000
| 8,000,000
| 8,000,000
| 8,000,000
| 600,000
| 600,000
| 600,000
|-
|-
|-
| ...
| ...
| ...
| ...
| ...
| ...
| ...
| ...
| ...
|-
|-
|-
| 63,072 × 10<sup>12</sup>
| 63,072 × 10<sup>12</sup>
63,072 & times; 10 sup 12 / sup
| 31,536 × 10<sup>12</sup> ns,<br />or 1 year
| 31,536 × 10<sup>12</sup> ns,<br />or 1 year
31,536 & times; 10 sup 12 / sup ns，br / or 1 year
| 1,375,000 ns,<br />or 1.375 milliseconds
| 1,375,000 ns,<br />or 1.375 milliseconds
| 1,375,000 ns，br / or 1.375 milliseconds
|}
|}
|}
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 [[logarithm]]ic growth rate. Quadrupling the input size only increases the run time by a [[wiktionary:Constant|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，因为它运行的算法增长速度要慢得多。
===Orders of growth===
{{main|Big O notation}}
Informally, an algorithm can be said to exhibit a growth rate on the order of a [[Function (mathematics)|mathematical function]] if beyond a certain input size ''n'', the function {{tmath|f(n)}} times a positive constant provides an [[Asymptotic analysis|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 {{tmath|c \times f(n)}}. This concept is frequently expressed using Big O notation. For example, since the run-time of [[insertion sort]] [[quadratic growth|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)的顺序。
Big O notation is a convenient way to express the [[Best, worst and average case|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 {{math|''O''(''n'' log ''n'')}}.
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) ，但是平均情况下的运行时是。
===Empirical orders of growth===
Assuming the execution time follows power rule, ''{{math|t ≈ k n<sup>a</sup>}}'', the coefficient ''a'' can be found <ref>[http://rjlipton.wordpress.com/2009/07/24/how-to-avoid-o-abuse-and-bribes/ How To Avoid O-Abuse and Bribes] {{Webarchive|url=https://web.archive.org/web/20170308175036/https://rjlipton.wordpress.com/2009/07/24/how-to-avoid-o-abuse-and-bribes/ |date=2017-03-08 }}, at the blog "Gödel's Lost Letter and P=NP" by R. J. Lipton, professor of Computer Science at Georgia Tech, recounting idea by Robert Sedgewick</ref> by taking empirical measurements of run time <math>\{t_1, t_2\}</math> at some problem-size points <math>\{n_1, n_2\}</math>, and calculating <math>t_2/t_1 = (n_2/n_1)^a</math> so that <math>a = \log(t_2/t_1) / \log(n_2/n_1)</math>. In other words, this measures the slope of the empirical line on the [[log–log plot]] of execution time vs. problem size, at some size point. If the order of growth indeed follows the power rule (and so the line on log–log plot is indeed a straight line), the empirical value of ''a'' will stay constant at different ranges, and if not, it will change (and the line is a curved line) - but still could serve for comparison of any two given algorithms as to their ''empirical local orders of growth'' behaviour. Applied to the above table:
Assuming the execution time follows power rule, , the coefficient a can be found by taking empirical measurements of run time <math>\{t_1, t_2\}</math> at some problem-size points <math>\{n_1, n_2\}</math>, and calculating <math>t_2/t_1 = (n_2/n_1)^a</math> so that <math>a = \log(t_2/t_1) / \log(n_2/n_1)</math>. In other words, this measures the slope of the empirical line on the log–log plot of execution time vs. problem size, at some size point. If the order of growth indeed follows the power rule (and so the line on log–log plot is indeed a straight line), the empirical value of a will stay constant at different ranges, and if not, it will change (and the line is a curved line) - but still could serve for comparison of any two given algorithms as to their empirical local orders of growth behaviour. Applied to the above table:
假设执行时间服从幂规则，系数 a 可以通过对运行时数学 t1，t2 / math 在某些问题大小点上的数学 n1，n2 / math 进行经验测量，然后计算数学 t2 / t1(n2 / n1) ^ a / math，从而得到数学 a / log (t2 / t1) / log (n2 / n1) / math。换句话说，在某个尺寸点上，这可以度量执行时间与问题大小的对数-对数图上经验曲线的斜率。如果增长的次序确实遵循幂次规则(因此对数曲线确实是一条直线) ，那么 a 的经验值将在不同的范围内保持不变，如果不是，它将发生变化(而且这条直线是一条曲线)——但仍然可以用于比较任何两个给定算法的经验局部增长行为次序。应用于上表:
{| class="wikitable"
{| class="wikitable"
{ | class“ wikitable”
|-_
|-_
|-_
! ''n'' (list size)
! n (list size)
!N (列表大小)
! Computer A run-time<br />(in [[nanosecond]]s)
! Computer A run-time<br />(in nanoseconds)
!运行时 br / (以纳秒为单位)
! Local order of growth<br />(n^_)
! Local order of growth<br />(n^_)
!生长 br / (n ^)的局部序
! Computer B run-time<br />(in [[nanosecond]]s)
! Computer B run-time<br />(in nanoseconds)
!计算机 b 运行时 br / (以纳秒为单位)
! Local order of growth<br />(n^_)
! Local order of growth<br />(n^_)
!生长 br / (n ^)的局部序
|-
|-
|-
| 15
| 15
| 15
| 7
| 7
| 7
|
|
|
| 100,000
| 100,000
| 100,000
|
|
|
|-
|-
|-
| 65
| 65
| 65
| 32
| 32
| 32
| 1.04
| 1.04
| 1.04
| 150,000
| 150,000
| 150,000
| 0.28
| 0.28
| 0.28
|-
|-
|-
| 250
| 250
| 250
| 125
| 125
| 125
| 1.01
| 1.01
| 1.01
| 200,000
| 200,000
| 200,000
| 0.21
| 0.21
| 0.21
|-
|-
|-
| 1,000
| 1,000
| 1,000
| 500
| 500
| 500
| 1.00
| 1.00
| 1.00
| 250,000
| 250,000
| 250,000
| 0.16
| 0.16
| 0.16
|-
|-
|-
| ...
| ...
| ...
| ...
| ...
| ...
|
|
|
| ...
| ...
| ...
|
|
|
|-
|-
|-
| 1,000,000
| 1,000,000
| 1,000,000
| 500,000
| 500,000
| 500,000
| 1.00
| 1.00
| 1.00
| 500,000
| 500,000
| 500,000
| 0.10
| 0.10
| 0.10
|-
|-
|-
| 4,000,000
| 4,000,000
| 4,000,000
| 2,000,000
| 2,000,000
| 2,000,000
| 1.00
| 1.00
| 1.00
| 550,000
| 550,000
| 550,000
| 0.07
| 0.07
| 0.07
|-
|-
|-
| 16,000,000
| 16,000,000
| 16,000,000
| 8,000,000
| 8,000,000
| 8,000,000
| 1.00
| 1.00
| 1.00
| 600,000
| 600,000
| 600,000
| 0.06
| 0.06
| 0.06
|-
|-
|-
| ...
| ...
| ...
| ...
| ...
| ...
|
|
|
| ...
| ...
| ...
|
|
|
|}
|}
|}
It is clearly seen that the first algorithm exhibits a linear order of growth indeed following the power rule. The empirical values for the second one are diminishing rapidly, suggesting it follows another rule of growth and in any case has much lower local orders of growth (and improving further still), empirically, than the first one.
It is clearly seen that the first algorithm exhibits a linear order of growth indeed following the power rule. The empirical values for the second one are diminishing rapidly, suggesting it follows another rule of growth and in any case has much lower local orders of growth (and improving further still), empirically, than the first one.
可以清楚地看到，第一个算法展示了一个线性增长序列，确实遵循幂规则。第二个经验值正在迅速递减，这表明它遵循了另一条增长规律，而且无论如何，从经验上看，当地的增长订单(以及进一步的增长)远低于第一个。
=== Evaluating run-time complexity ===
The run-time complexity for the worst-case scenario of a given algorithm can sometimes be evaluated by examining the structure of the algorithm and making some simplifying assumptions. Consider the following [[pseudocode]]:
The run-time complexity for the worst-case scenario of a given algorithm can sometimes be evaluated by examining the structure of the algorithm and making some simplifying assumptions. Consider the following pseudocode:
给定算法的运行绝境求生手册复杂度有时可以通过检查算法的结构和做一些简化的假设来评估。考虑下面的伪代码:
1 ''get a positive integer n from input''
1 get a positive integer n from input
1从输入得到一个正整数 n
2 '''if''' n > 10
2 if n > 10
2 if n 10
3 '''print''' "This might take a while..."
3 print "This might take a while..."
“这可能需要一段时间... ... ”
4 '''for''' i = 1 '''to''' n
4 for i = 1 to n
4表示 i 1到 n
5 '''for''' j = 1 '''to''' i
5 for j = 1 to i
5表示 j1表示 i
6 '''print''' i * j
6 print i * j
6 print i * j
7 '''print''' "Done!"
7 print "Done!"
打印7页“完成! ”
A given computer will take a [[DTIME|discrete amount of time]] to execute each of the [[Instruction (computer science)|instructions]] involved with carrying out this algorithm. The specific amount of time to carry out a given instruction will vary depending on which instruction is being executed and which computer is executing it, but on a conventional computer, this amount will be [[Deterministic system (mathematics)|deterministic]].<ref>However, this is not the case with a [[quantum computer]]</ref> Say that the actions carried out in step 1 are considered to consume time ''T''<sub>1</sub>, step 2 uses time ''T''<sub>2</sub>, and so forth.
A given computer will take a discrete amount of time to execute each of the instructions involved with carrying out this algorithm. The specific amount of time to carry out a given instruction will vary depending on which instruction is being executed and which computer is executing it, but on a conventional computer, this amount will be deterministic. Say that the actions carried out in step 1 are considered to consume time T<sub>1</sub>, step 2 uses time T<sub>2</sub>, and so forth.
给定的计算机将采取一个离散的时间量来执行与执行这个算法有关的每一个指令。执行给定指令的具体时间量取决于正在执行的指令和正在执行的计算机，但在传统计算机上，这个时间量是确定的。假设步骤1中执行的动作被认为消耗时间 t 子1 / 子，步骤2使用时间 t 子2 / 子，等等。
In the algorithm above, steps 1, 2 and 7 will only be run once. For a worst-case evaluation, it should be assumed that step 3 will be run as well. Thus the total amount of time to run steps 1-3 and step 7 is:
In the algorithm above, steps 1, 2 and 7 will only be run once. For a worst-case evaluation, it should be assumed that step 3 will be run as well. Thus the total amount of time to run steps 1-3 and step 7 is:
在上面的算法中，步骤1、2和7只运行一次。对于最坏情况的评估，应该假定步骤3也将运行。因此，运行步骤1-3和步骤7所需的总时间是:
:<math>T_1 + T_2 + T_3 + T_7. \,</math>
<math>T_1 + T_2 + T_3 + T_7. \,</math>
数学 t1 + t2 + t3 + t7。数学
The [[program loop|loops]] in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( ''n'' + 1 )
The loops in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( n + 1 )
步骤4、5和6中的循环更难计算。步骤4中的外部循环测试将执行(n + 1)
times (note that an extra step is required to terminate the for loop, hence n + 1 and not n executions), which will consume ''T''<sub>4</sub>( ''n'' + 1 ) time. The inner loop, on the other hand, is governed by the value of j, which [[iteration|iterates]] from 1 to ''i''. On the first pass through the outer loop, j iterates from 1 to 1: The inner loop makes one pass, so running the inner loop body (step 6) consumes ''T''<sub>6</sub> time, and the inner loop test (step 5) consumes 2''T''<sub>5</sub> time. During the next pass through the outer loop, j iterates from 1 to 2: the inner loop makes two passes, so running the inner loop body (step 6) consumes 2''T''<sub>6</sub> time, and the inner loop test (step 5) consumes 3''T''<sub>5</sub> time.
times (note that an extra step is required to terminate the for loop, hence n + 1 and not n executions), which will consume T<sub>4</sub>( n + 1 ) time. The inner loop, on the other hand, is governed by the value of j, which iterates from 1 to i. On the first pass through the outer loop, j iterates from 1 to 1: The inner loop makes one pass, so running the inner loop body (step 6) consumes T<sub>6</sub> time, and the inner loop test (step 5) consumes 2T<sub>5</sub> time. During the next pass through the outer loop, j iterates from 1 to 2: the inner loop makes two passes, so running the inner loop body (step 6) consumes 2T<sub>6</sub> time, and the inner loop test (step 5) consumes 3T<sub>5</sub> time.
时(注意，终止 for 循环需要一个额外的步骤，因此 n + 1而不是 n 次执行) ，这将消耗 t 小于4 / sub (n + 1)的时间。另一方面，内部循环由 j 的值控制，该值从1迭代到 i。在第一次通过外部循环时，j 迭代1到1: 内部循环通过一次，因此运行内部循环体(第6步)消耗 t 小于6 / 子时间，而内部循环测试(第5步)消耗2T 小于5 / 子时间。在下一次通过外部循环时，j 从1到2迭代: 内部循环进行两次通过，因此运行内部循环体(步骤6)消耗2T 子6 / 子时间，而内部循环测试(步骤5)消耗3T 子5 / 子时间。
Altogether, the total time required to run the inner loop body can be expressed as an [[arithmetic progression]]:
Altogether, the total time required to run the inner loop body can be expressed as an arithmetic progression:
总之，运行内部循环体所需的总时间可以用等差数列表示:
:<math>T_6 + 2T_6 + 3T_6 + \cdots + (n-1) T_6 + n T_6</math>
<math>T_6 + 2T_6 + 3T_6 + \cdots + (n-1) T_6 + n T_6</math>
数学 t6 + 2t6 + 3t6 + cdots + (n-1) t6 + n t6 / math
which can be [[factorization|factored]]<ref>It can be proven by [[Mathematical induction|induction]] that <math>1 + 2 + 3 + \cdots + (n-1) + n = \frac{n(n+1)}{2}</math></ref> as
which can be factored as
这可以作为一个因素
:<math>T_6 \left[ 1 + 2 + 3 + \cdots + (n-1) + n \right] = T_6 \left[ \frac{1}{2} (n^2 + n) \right] </math>
<math>T_6 \left[ 1 + 2 + 3 + \cdots + (n-1) + n \right] = T_6 \left[ \frac{1}{2} (n^2 + n) \right] </math>
数学 t6左[1 + 2 + 3 + cdots + (n-1) + n 右] t6左[ frac {1}{2}(n ^ 2 + n)右] / 数学
The total time required to run the outer loop test can be evaluated similarly:
The total time required to run the outer loop test can be evaluated similarly:
运行外部循环测试所需的总时间可以用类似的方法计算:
:<math>\begin{align}
<math>\begin{align}
数学 begin { align }
& 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1) T_5 + n T_5 + (n + 1) T_5\\
& 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1) T_5 + n T_5 + (n + 1) T_5\\
2t5 + 3t5 + 4t5 + cdots + (n-1) t5 + n t5 + (n + 1) t5
=\ &T_5 + 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1)T_5 + nT_5 + (n+1)T_5 - T_5
=\ &T_5 + 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1)T_5 + nT_5 + (n+1)T_5 - T_5
5 + 2t5 + 3t5 + 4t5 + cdots + (n-1) t5 + nT 5 + (n + 1) t5-t5
\end{align}</math>
\end{align}</math>
End { align } / math
which can be factored as
which can be factored as
这可以作为一个因素
:<math>\begin{align}
<math>\begin{align}
数学 begin { align }
& T_5 \left[ 1+2+3+\cdots + (n-1) + n + (n + 1) \right] - T_5 \\
& T_5 \left[ 1+2+3+\cdots + (n-1) + n + (n + 1) \right] - T_5 \\
& t5左[1 + 2 + 3 + cdots + (n-1) + n + (n + 1)右]-t5
=& \left[ \frac{1}{2} (n^2 + n) \right] T_5 + (n + 1)T_5 - T_5 \\
=& \left[ \frac{1}{2} (n^2 + n) \right] T_5 + (n + 1)T_5 - T_5 \\
左[ frac {1}{2}(n ^ 2 + n)右] t5 + (n + 1) t5-t5
=& T_5 \left[ \frac{1}{2} (n^2 + n) \right] + n T_5 \\
=& T_5 \left[ \frac{1}{2} (n^2 + n) \right] + n T_5 \\
& t 5左[ frac {1}{2}(n ^ 2 + n)右] + n t 5
=& \left[ \frac{1}{2} (n^2 + 3n) \right] T_5
=& \left[ \frac{1}{2} (n^2 + 3n) \right] T_5
左[ frac {1}{2}(n ^ 2 + 3n)右] t 5
\end{align}</math>
\end{align}</math>
End { align } / math
Therefore, the total running time for this algorithm is:
Therefore, the total running time for this algorithm is:
因此，此算法的总运行时间为:
:<math>f(n) = T_1 + T_2 + T_3 + T_7 + (n + 1)T_4 + \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2+3n) \right] T_5 </math>
<math>f(n) = T_1 + T_2 + T_3 + T_7 + (n + 1)T_4 + \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2+3n) \right] T_5 </math>
数学 f (n) t1 + t2 + t3 + t7 + (n + 1) t4 + 左[ frac {1}(n ^ 2 + n)右] t6 + 左[ frac {1}(n ^ 2 + 3 n)右] t5 / math
which [[reduction (mathematics)|reduces]] to
which reduces to
这就简化为
:<math>f(n) = \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7
<math>f(n) = \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7
数学 f (n)左[ frac {1}{2}(n ^ 2 + n)右] t6 + 左[ frac {1}(n ^ 2 + 3n)右] t5 + (n + 1) t4 + t1 + t2 + t3 + t7
</math>
</math>
数学
As a [[rule-of-thumb]], one can assume that the highest-order term in any given function dominates its rate of growth and thus defines its run-time order. In this example, n<sup>2</sup> is the highest-order term, so one can conclude that f(n) = O(n<sup>2</sup>). Formally this can be proven as follows:
As a rule-of-thumb, one can assume that the highest-order term in any given function dominates its rate of growth and thus defines its run-time order. In this example, n<sup>2</sup> is the highest-order term, so one can conclude that f(n) = O(n<sup>2</sup>). Formally this can be proven as follows:
作为一个经验法则，我们可以假设任何给定函数中的最高阶项主导了它的增长率，从而定义了它的运行时序。在这个例子中，n sup 2 / sup 是最高阶项，因此可以得出 f (n) o (n sup 2 / sup)。在形式上，这可以证明如下:
{{quote|Prove that <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2,\ n \ge n_0</math>
{{quote|Prove that <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2,\ n \ge n_0</math>
{引号 | 证明数学左[ frac {1}{2}(n ^ 2 + n)右] t6 + 左[ frac {1}(n ^ 2 + 3n)右] t5 + (n + 1) t4 + t1 + t2 + t3 + t7 cn ^ 2， n ge n0 / math
<br /><br />
<br /><br />
Br / br /
<math>\begin{align}
<math>\begin{align}
数学 begin { align }
&\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7\\
&\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7\\
左[ frac {1}{2}(n ^ 2 + n)右] t6 + 左[ frac {1}{2}(n ^ 2 + 3n)右] t5 + (n + 1) t4 + t1 + t2 + t3 + t7
\le &( n^2 + n )T_6 + ( n^2 + 3n )T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \ (\text{for } n \ge 0 )
\le &( n^2 + n )T_6 + ( n^2 + 3n )T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \ (\text{for } n \ge 0 )
(n ^ 2 + n) t6 + (n ^ 2 + 3n) t5 + (n + 1) t4 + t1 + t2 + t3 + t7(for } n ge0)
\end{align}</math>
\end{align}</math>
End { align } / math
<br /><br />
<br /><br />
Br / br /
Let ''k'' be a constant greater than or equal to [''T''<sub>1</sub>..''T''<sub>7</sub>]
Let k be a constant greater than or equal to [T<sub>1</sub>..T<sub>7</sub>]
设 k 为大于或等于[ t 小于1 / 小于. . t 小于7 / 小于]的常数
<br /><br />
<br /><br />
Br / br /
<math>\begin{align}
<math>\begin{align}
数学 begin { align }
&T_6( n^2 + n ) + T_5( n^2 + 3n ) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k( n^2 + n ) + k( n^2 + 3n ) + kn + 5k\\
&T_6( n^2 + n ) + T_5( n^2 + 3n ) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k( n^2 + n ) + k( n^2 + 3n ) + kn + 5k\\
& t6(n ^ 2 + n) + t5(n ^ 2 + 3n) + (n + 1) t4 + t1 + t2 + t3 + t7 le k (n ^ 2 + n) + k (n ^ 2 + 3n) + kn + 5k
= &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
= &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
= &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
\end{align}</math>
\end{align}</math>
End { align } / math
<br /><br />
<br /><br />
Br / br /
Therefore <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2, n \ge n_0 \text{ for } c = 12k, n_0 = 1</math>
Therefore <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2, n \ge n_0 \text{ for } c = 12k, n_0 = 1</math>
因此，数学左[ frac {1}{2}(n ^ 2 + n)右] t6 + 左[ frac {1}(n ^ 2 + 3n)右] t5 + (n + 1) t4 + t1 + t2 + t3 + t7 le ^ cn 2，n ge n 0 text { for } c12k，n 01 / math
}}
}}
}}
A more [[elegance|elegant]] approach to analyzing this algorithm would be to declare that [''T''<sub>1</sub>..''T''<sub>7</sub>] are all equal to one unit of time, in a system of units chosen so that one unit is greater than or equal to the actual times for these steps. This would mean that the algorithm's running time breaks down as follows:<ref>This approach, unlike the above approach, neglects the constant time consumed by the loop tests which terminate their respective loops, but it is [[Trivial (mathematics)|trivial]] to prove that such omission does not affect the final result</ref>
A more elegant approach to analyzing this algorithm would be to declare that [T<sub>1</sub>..T<sub>7</sub>] are all equal to one unit of time, in a system of units chosen so that one unit is greater than or equal to the actual times for these steps. This would mean that the algorithm's running time breaks down as follows:
分析此算法的一个更优雅的方法是声明[ t 子1 / sub。 . T 小于7 / sub ]都等于一个时间单位，在一个选择的单位系统中，一个单位大于或等于这些步骤的实际时间。这意味着该算法的运行时间分解如下:
{{quote|<math>4+\sum_{i=1}^n i\leq 4+\sum_{i=1}^n n=4+n^2\leq5n^2 \ (\text{for } n \ge 1) =O(n^2).</math>}}
===Growth rate analysis of other resources===
The methodology of run-time analysis can also be utilized for predicting other growth rates, such as consumption of [[DSPACE|memory space]]. As an example, consider the following pseudocode which manages and reallocates memory usage by a program based on the size of a [[computer file|file]] which that program manages:
The methodology of run-time analysis can also be utilized for predicting other growth rates, such as consumption of memory space. As an example, consider the following pseudocode which manages and reallocates memory usage by a program based on the size of a file which that program manages:
运行时分析的方法也可用于预测其他增长率，如内存空间的消耗。例如，考虑下面的伪代码，它根据程序管理的文件的大小来管理和重新分配程序的内存使用:
'''while''' ''file is still open:''
while file is still open:
在文件还开着的时候:
'''let''' n = ''size of file''
let n = size of file
文件大小 n
'''for''' ''every 100,000 [[kilobyte]]s of increase in file size''
for every 100,000 kilobytes of increase in file size
文件大小每增加10万千字节
''double the amount of memory reserved''
double the amount of memory reserved
保留的内存量翻倍
In this instance, as the file size n increases, memory will be consumed at an [[exponential growth]] rate, which is order O(2<sup>n</sup>). This is an extremely rapid and most likely unmanageable growth rate for consumption of memory [[Resource (computer science)|resources]].
In this instance, as the file size n increases, memory will be consumed at an exponential growth rate, which is order O(2<sup>n</sup>). This is an extremely rapid and most likely unmanageable growth rate for consumption of memory resources.
在这个例子中，随着文件大小 n 的增加，内存消耗的速度将达到指数增长，即 o (2 sup n / sup)。对于内存资源的消耗，这是一个极其快速且最有可能无法控制的增长率。
==Relevance==
Algorithm analysis is important in practice because the accidental or unintentional use of an inefficient algorithm can significantly impact system performance. In time-sensitive applications, an algorithm taking too long to run can render its results outdated or useless. An inefficient algorithm can also end up requiring an uneconomical amount of computing power or storage in order to run, again rendering it practically useless.
Algorithm analysis is important in practice because the accidental or unintentional use of an inefficient algorithm can significantly impact system performance. In time-sensitive applications, an algorithm taking too long to run can render its results outdated or useless. An inefficient algorithm can also end up requiring an uneconomical amount of computing power or storage in order to run, again rendering it practically useless.
算法分析在实践中非常重要，因为偶然或无意地使用低效算法会显著影响系统性能。在对时间敏感的应用程序中，运行时间过长的算法可能使其结果过时或无用。一个低效的算法也可能最终需要不经济的计算能力或存储量才能运行，再一次使它变得毫无用处。
==Constant factors==
Analysis of algorithms typically focuses on the asymptotic performance, particularly at the elementary level, but in practical applications constant factors are important, and real-world data is in practice always limited in size. The limit is typically the size of addressable memory, so on 32-bit machines 2<sup>32</sup> = 4 GiB (greater if [[segmented memory]] is used) and on 64-bit machines 2<sup>64</sup> = 16 EiB. Thus given a limited size, an order of growth (time or space) can be replaced by a constant factor, and in this sense all practical algorithms are O(1) for a large enough constant, or for small enough data.
Analysis of algorithms typically focuses on the asymptotic performance, particularly at the elementary level, but in practical applications constant factors are important, and real-world data is in practice always limited in size. The limit is typically the size of addressable memory, so on 32-bit machines 2<sup>32</sup> = 4 GiB (greater if segmented memory is used) and on 64-bit machines 2<sup>64</sup> = 16 EiB. Thus given a limited size, an order of growth (time or space) can be replaced by a constant factor, and in this sense all practical algorithms are O(1) for a large enough constant, or for small enough data.
对算法的分析通常侧重于渐近性能，特别是在初级水平，但在实际应用中，常数因素是重要的，而实际数据在规模上总是有限的。这个限制通常是可寻址内存的大小，所以在32位机器2 sup 32 / sup 4gib (如果使用分段内存则更大)和64位机器2 sup 64 / sup 16 EiB 上。因此，给定一个有限的大小，一个增长的顺序(时间或空间)可以被一个常量因子所取代，在这个意义上，所有实用的算法对于足够大的常量或足够小的数据都是 o (1)。
This interpretation is primarily useful for functions that grow extremely slowly: (binary) [[iterated logarithm]] (log<sup>*</sup>) is less than 5 for all practical data (2<sup>65536</sup> bits); (binary) log-log (log log ''n'') is less than 6 for virtually all practical data (2<sup>64</sup> bits); and binary log (log ''n'') is less than 64 for virtually all practical data (2<sup>64</sup> bits). An algorithm with non-constant complexity may nonetheless be more efficient than an algorithm with constant complexity on practical data if the overhead of the constant time algorithm results in a larger constant factor, e.g., one may have <math>K > k \log \log n</math> so long as <math>K/k > 6</math> and <math>n < 2^{2^6} = 2^{64}</math>.
This interpretation is primarily useful for functions that grow extremely slowly: (binary) iterated logarithm (log<sup>*</sup>) is less than 5 for all practical data (2<sup>65536</sup> bits); (binary) log-log (log log n) is less than 6 for virtually all practical data (2<sup>64</sup> bits); and binary log (log n) is less than 64 for virtually all practical data (2<sup>64</sup> bits). An algorithm with non-constant complexity may nonetheless be more efficient than an algorithm with constant complexity on practical data if the overhead of the constant time algorithm results in a larger constant factor, e.g., one may have <math>K > k \log \log n</math> so long as <math>K/k > 6</math> and <math>n < 2^{2^6} = 2^{64}</math>.
这种解释主要适用于增长极其缓慢的函数: (二进制)迭代对数(log sup * / sup)对所有实际数据(2 sup 65536 / sup bit)小于5; (二进制) log-log (log n)对几乎所有实际数据(2 sup 64 / sup bit)小于6; 二进制 log (log n)对几乎所有实际数据(2 sup 64 / sup bits)小于64。如果常量时间算法的开销导致一个更大的常量因子，那么非常量复杂度的算法可能比实际数据上的常量复杂度算法更有效，例如，只要有数学 k / k6 / math 和数学 n2 ^ {2 ^ 6}2 ^ {64} / math，就可能有数学 k log n / math。
For large data linear or quadratic factors cannot be ignored, but for small data an asymptotically inefficient algorithm may be more efficient. This is particularly used in [[hybrid algorithm]]s, like [[Timsort]], which use an asymptotically efficient algorithm (here [[merge sort]], with time complexity <math>n \log n</math>), but switch to an asymptotically inefficient algorithm (here [[insertion sort]], with time complexity <math>n^2</math>) for small data, as the simpler algorithm is faster on small data.
For large data linear or quadratic factors cannot be ignored, but for small data an asymptotically inefficient algorithm may be more efficient. This is particularly used in hybrid algorithms, like Timsort, which use an asymptotically efficient algorithm (here merge sort, with time complexity <math>n \log n</math>), but switch to an asymptotically inefficient algorithm (here insertion sort, with time complexity <math>n^2</math>) for small data, as the simpler algorithm is faster on small data.
对于大数据不能忽略线性因子或二次因子，但对于小数据，渐近低效算法可能更有效。这在混合算法中尤其常用，比如 Timsort，它使用一种渐近有效的算法(在这里使用合并排序，时间复杂度数学 n log n / math) ，但是对于小数据切换到一种渐近低效的算法(在这里使用插入排序，时间复杂度数学 n ^ 2 / math) ，因为更简单的算法在小数据上更快。
==See also==
* [[Amortized analysis]]
* [[Analysis of parallel algorithms]]
* [[Asymptotic computational complexity]]
* [[Best, worst and average case]]
* [[Big O notation]]
* [[Computational complexity theory]]
* [[Master theorem (analysis of algorithms)]]
* [[NP-Complete]]
* [[Numerical analysis]]
* [[Polynomial time]]
* [[Program optimization]]
* [[Profiling (computer programming)]]
* [[Scalability]]
* [[Smoothed analysis]]
* [[Termination analysis]] — the subproblem of checking whether a program will terminate at all
* [[Time complexity]] — includes table of orders of growth for common algorithms
* [[Information-based complexity]]
==Notes==
{{reflist}}
==References==
*{{Cite book |authorlink=Thomas H. Cormen |first=Thomas H. |last=Cormen |authorlink2=Charles E. Leiserson |first2=Charles E. |last2=Leiserson |authorlink3=Ronald L. Rivest |first3=Ronald L. |last3=Rivest |lastauthoramp=yes |authorlink4=Clifford Stein |first4=Clifford |last4=Stein |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press and McGraw-Hill |location=Cambridge, MA |year=2001 |isbn=0-262-03293-7 |others=Chapter 1: Foundations |pages=3–122 }}
*{{Cite book |title=Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching |edition=3rd |authorlink=Robert Sedgewick (computer scientist) |first=Robert |last=Sedgewick |location=Reading, MA |publisher=Addison-Wesley Professional |year=1998 |isbn=978-0-201-31452-6 |url-access=registration |url=https://archive.org/details/algorithmsinc00sedg }}
*{{Cite book |title=[[The Art of Computer Programming]] |authorlink=Donald Knuth |first=Donald |last=Knuth |location= |publisher=Addison-Wesley |isbn= |year= }}
*{{Cite book |first=Daniel A. |last=Greene |first2=Donald E. |last2=Knuth |title=Mathematics for the Analysis of Algorithms |edition=Second |location= |publisher=Birkhäuser |year=1982 |isbn=3-7643-3102-X }}
*{{Cite book |authorlink=Oded Goldreich |first=Oded |last=Goldreich |title=Computational Complexity: A Conceptual Perspective |location= |publisher=[[Cambridge University Press]] |year=2010 |isbn=978-0-521-88473-0 }}
==External links==
*{{Commonscatinline}}
{{Computer science}}
{{DEFAULTSORT:Analysis Of Algorithms}}
[[Category:Analysis of algorithms| ]]
[[Category:Computational complexity theory]]
Category:Computational complexity theory
类别: 计算复杂性理论
<noinclude>
<small>This page was moved from [[wikipedia:en:Analysis of algorithms]]. Its edit history can be viewed at [[算法分析/edithistory]]</small></noinclude>
[[Category:待整理页面]]
{{more footnotes|date=March 2010}}
[[File:Binary search vs Linear search example svg.svg|thumb|For looking up a given entry in a given ordered list, both the [[binary search algorithm|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<sub>2</sub>(''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 (shown in {{color|#008080|cyan}}) and linear ({{color|#800080|magenta}}) search, respectively.]]
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<sub>2</sub>(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 (shown in ) and linear () search, respectively.]]
二进制和线性搜索算法(忽略排序)可以使用。对前者和后者的分析表明，对于一个长度 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]]
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 的对应关系
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.
在计算机科学中，算法分析是查找算法计算复杂性的过程——执行它们所需的时间、存储空间或其他资源的数量。通常，这涉及到确定一个函数，该函数将算法的输入长度与它所采取的步骤数(其时间复杂度)或它所使用的存储位置数(其空间复杂度)联系起来。当这个函数的值很小，或者与输入大小的增长相比增长缓慢时，一个算法被认为是有效的。相同长度的不同输入可能导致算法具有不同的行为，因此最佳、最差和平均情况描述都可能具有实际意义。当没有另外指定时，描述算法性能的函数通常是一个上界，由算法的最坏情况输入确定。
The term "analysis of algorithms" was coined by [[Donald Knuth]].<ref>{{cite web|url=https://web.archive.org/web/20160828152021/http://www-cs-faculty.stanford.edu/~uno/news.html|title=Knuth: Recent News|date=28 August 2016|website=web.archive.org}}</ref> 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 [[Algorithmic efficiency|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 创造的。算法分析是更广泛的计算复杂性理论分析的重要组成部分，它为任何解决给定计算问题的算法所需的资源提供理论估计。这些估计为寻找有效算法的合理方向提供了洞察力。
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.
在算法的理论分析中，通常是在渐近意义上估计它们的复杂性，即对任意大的输入估计复杂性函数。大 o 符号、大 -omega 符号和大 -theta 符号被用于此目的。例如，二进制搜索被称为以与被搜索的排序列表长度的对数成正比的若干步长运行，或者以 o (log (n))通俗地称为“对数时间”。通常使用渐近估计，因为同一算法的不同实现可能在效率上有所不同。然而，给定算法的任何两个“合理”实现的效率是由一个称为隐常数的常数乘法因子相关联的。
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.
精确(而非渐近)的效率措施有时可以计算，但他们通常需要一定的假设关于特定的实施算法，称为计算模型。一个计算模型可以用抽象计算机来定义，例如图灵机，和 / 或通过假设某些操作在单位时间内执行。
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<sub>2</sub> ''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<sub>2</sub> n + 1 time units are needed to return an answer.
例如，如果我们应用二进制搜索的排序列表有 n 个元素，并且我们可以保证列表中每个元素的查找都可以在单位时间内完成，那么最多需要 log 子2 / sub 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.-->
<！ ——对于实际实现和使用算法的人来说，精确的效率测量是有用的，因为算法更加精确，因此能够让他们知道自己在执行过程中预计会花费多少时间。对某些人来说(例如:。一个隐藏的常数可以决定成功和失败。——
== Cost models ==
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.
时间效率的估计取决于我们对步骤的定义。为了使分析有效地对应于实际执行时间，执行一个步骤所需的时间必须保证在一个常数之上。这里我们必须小心; 例如，有些分析把两个数字的相加计算为一个步骤。在某些情况下，这种假设可能是不正当的。例如，如果计算中涉及的数字可能是任意大的，那么单个加法所需的时间就不能再假定为常数。
Two cost models are generally used:<ref name="AhoHopcroft1974">{{cite book|author1=Alfred V. Aho|author2=John E. Hopcroft|author3=Jeffrey D. Ullman|title=The design and analysis of computer algorithms|url=https://archive.org/details/designanalysisof00ahoarich|url-access=registration|year=1974|publisher=Addison-Wesley Pub. Co.}}, section 1.3</ref><ref name="Hromkovič2004">{{cite book|author=Juraj Hromkovič|title=Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography|url=https://books.google.com/books?id=KpNet-n262QC&pg=PA177|year=2004|publisher=Springer|isbn=978-3-540-14015-3|pages=177–178}}</ref><ref name="Ausiello1999">{{cite book|author=Giorgio Ausiello|title=Complexity and approximation: combinatorial optimization problems and their approximability properties|url=https://books.google.com/books?id=Yxxw90d9AuMC&pg=PA3|year=1999|publisher=Springer|isbn=978-3-540-65431-5|pages=3–8}}</ref><ref name=Wegener20>{{Citation|last1=Wegener|first1=Ingo|title=Complexity theory: exploring the limits of efficient algorithms|publisher=[[Springer-Verlag]]|location=Berlin, New York|isbn=978-3-540-21045-0|year=2005|page=20|url=https://books.google.com/books?id=u7DZSDSUYlQC&pg=PA20}}</ref><ref name="Tarjan1983">{{cite book|author=[[Robert Endre Tarjan]]|title=Data structures and network algorithms|url=https://books.google.com/books?id=JiC7mIqg-X4C&pg=PA3|year=1983|publisher=SIAM|isbn=978-0-89871-187-5|pages=3–7}}</ref>
Two cost models are generally used:
通常使用两种成本模型:
* 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 latter is more cumbersome to use, so it's only employed when necessary, for example in the analysis of [[arbitrary-precision arithmetic]] algorithms, like those used in [[cryptography]].
The latter is more cumbersome to use, so it's only employed when necessary, for example in the analysis of arbitrary-precision arithmetic algorithms, like those used in cryptography.
后者使用起来比较麻烦，所以只有在必要的时候才会使用，例如在分析高精度计算算法时，就像那些在密码学中使用的算法。
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.<ref>[https://cstheory.stackexchange.com/q/608 Examples of the price of abstraction?], cstheory.stackexchange.com</ref>
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 is a theoretical classification that estimates and anticipates the increase in ''[[DTIME|running time]]'' (or run-time) of an [[algorithm]] as its ''[[Information|input size]]'' (usually denoted as ''n'') increases. Run-time efficiency is a topic of great interest in [[computer science]]: A [[Computer program|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)的增加而估计和预期运行时间(或运行时间)的增加。运行时效率是计算机科学中非常感兴趣的话题: 一个程序可能需要几秒钟、几小时甚至几年才能完成执行，这取决于它实现的算法。虽然软件分析技术可用于在实践中测量算法的运行时间，但它们不能为所有无限多可能的输入提供计时数据; 后者只能通过运行时间分析的理论方法来实现。
===Shortcomings of empirical metrics===
Since algorithms are [[platform-independent]] (i.e. a given algorithm can be implemented in an arbitrary [[programming language]] on an arbitrary [[computer]] running an arbitrary [[operating system]]), there are additional significant drawbacks to using an [[empirical]] approach to gauge the comparative performance of a given set of algorithms.
Since algorithms are platform-independent (i.e. a given algorithm can be implemented in an arbitrary programming language on an arbitrary computer running an arbitrary operating system), there are additional significant drawbacks to using an empirical approach to gauge the comparative performance of a given set of algorithms.
由于算法是独立于平台的(即。一个给定的算法可以在任意运行任意操作系统的计算机上用任意编程语言实现) ，使用经验方法来衡量一组给定算法的比较性能还有一个明显的缺点。
Take as an example a program that looks up a specific entry in a [[collation|sorted]] [[list (computing)|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 (computing)|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 计算机速度要慢得多。在运行各自程序的两台计算机上进行的基准测试可能看起来如下所示:
{| class="wikitable"
{| class="wikitable"
{ | class“ wikitable”
|-
|-
|-
! ''n'' (list size)
! n (list size)
!N (列表大小)
! Computer A run-time<br />(in [[nanosecond]]s)
! Computer A run-time<br />(in nanoseconds)
!运行时 br / (以纳秒为单位)
! Computer B run-time<br />(in [[nanosecond]]s)
! Computer B run-time<br />(in nanoseconds)
!计算机 b 运行时 br / (以纳秒为单位)
|-
|-
|-
| 16
| 16
| 16
| 8
| 8
| 8
| 100,000
| 100,000
| 100,000
|-
|-
|-
| 63
| 63
| 63
| 32
| 32
| 32
| 150,000
| 150,000
| 150,000
|-
|-
|-
| 250
| 250
| 250
| 125
| 125
| 125
| 200,000
| 200,000
| 200,000
|-
|-
|-
| 1,000
| 1,000
| 1,000
| 500
| 500
| 500
| 250,000
| 250,000
| 250,000
|}
|}
|}
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:
基于这些度量，我们很容易得出结论: a 计算机运行的算法在效率上远远优于 b 计算机。然而，如果输入列表的大小增加到一个足够大的数字，这个结论就会被戏剧性地证明是错误的:
{| class="wikitable"
{| class="wikitable"
{ | class“ wikitable”
|-
|-
|-
! ''n'' (list size)
! n (list size)
!N (列表大小)
! Computer A run-time<br />(in [[nanosecond]]s)
! Computer A run-time<br />(in nanoseconds)
!运行时 br / (以纳秒为单位)
! Computer B run-time<br />(in [[nanosecond]]s)
! Computer B run-time<br />(in nanoseconds)
!计算机 b 运行时 br / (以纳秒为单位)
|-
|-
|-
| 16
| 16
| 16
| 8
| 8
| 8
| 100,000
| 100,000
| 100,000
|-
|-
|-
| 63
| 63
| 63
| 32
| 32
| 32
| 150,000
| 150,000
| 150,000
|-
|-
|-
| 250
| 250
| 250
| 125
| 125
| 125
| 200,000
| 200,000
| 200,000
|-
|-
|-
| 1,000
| 1,000
| 1,000
| 500
| 500
| 500
| 250,000
| 250,000
| 250,000
|-
|-
|-
| ...
| ...
| ...
| ...
| ...
| ...
| ...
| ...
| ...
|-
|-
|-
| 1,000,000
| 1,000,000
| 1,000,000
| 500,000
| 500,000
| 500,000
| 500,000
| 500,000
| 500,000
|-
|-
|-
| 4,000,000
| 4,000,000
| 4,000,000
| 2,000,000
| 2,000,000
| 2,000,000
| 550,000
| 550,000
| 550,000
|-
|-
|-
| 16,000,000
| 16,000,000
| 16,000,000
| 8,000,000
| 8,000,000
| 8,000,000
| 600,000
| 600,000
| 600,000
|-
|-
|-
| ...
| ...
| ...
| ...
| ...
| ...
| ...
| ...
| ...
|-
|-
|-
| 63,072 × 10<sup>12</sup>
| 63,072 × 10<sup>12</sup>
63,072 & times; 10 sup 12 / sup
| 31,536 × 10<sup>12</sup> ns,<br />or 1 year
| 31,536 × 10<sup>12</sup> ns,<br />or 1 year
31,536 & times; 10 sup 12 / sup ns，br / or 1 year
| 1,375,000 ns,<br />or 1.375 milliseconds
| 1,375,000 ns,<br />or 1.375 milliseconds
| 1,375,000 ns，br / or 1.375 milliseconds
|}
|}
|}
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 [[logarithm]]ic growth rate. Quadrupling the input size only increases the run time by a [[wiktionary:Constant|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，因为它运行的算法增长速度要慢得多。
===Orders of growth===
{{main|Big O notation}}
Informally, an algorithm can be said to exhibit a growth rate on the order of a [[Function (mathematics)|mathematical function]] if beyond a certain input size ''n'', the function {{tmath|f(n)}} times a positive constant provides an [[Asymptotic analysis|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 {{tmath|c \times f(n)}}. This concept is frequently expressed using Big O notation. For example, since the run-time of [[insertion sort]] [[quadratic growth|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)的顺序。
Big O notation is a convenient way to express the [[Best, worst and average case|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 {{math|''O''(''n'' log ''n'')}}.
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) ，但是平均情况下的运行时是。
===Empirical orders of growth===
Assuming the execution time follows power rule, ''{{math|t ≈ k n<sup>a</sup>}}'', the coefficient ''a'' can be found <ref>[http://rjlipton.wordpress.com/2009/07/24/how-to-avoid-o-abuse-and-bribes/ How To Avoid O-Abuse and Bribes] {{Webarchive|url=https://web.archive.org/web/20170308175036/https://rjlipton.wordpress.com/2009/07/24/how-to-avoid-o-abuse-and-bribes/ |date=2017-03-08 }}, at the blog "Gödel's Lost Letter and P=NP" by R. J. Lipton, professor of Computer Science at Georgia Tech, recounting idea by Robert Sedgewick</ref> by taking empirical measurements of run time <math>\{t_1, t_2\}</math> at some problem-size points <math>\{n_1, n_2\}</math>, and calculating <math>t_2/t_1 = (n_2/n_1)^a</math> so that <math>a = \log(t_2/t_1) / \log(n_2/n_1)</math>. In other words, this measures the slope of the empirical line on the [[log–log plot]] of execution time vs. problem size, at some size point. If the order of growth indeed follows the power rule (and so the line on log–log plot is indeed a straight line), the empirical value of ''a'' will stay constant at different ranges, and if not, it will change (and the line is a curved line) - but still could serve for comparison of any two given algorithms as to their ''empirical local orders of growth'' behaviour. Applied to the above table:
Assuming the execution time follows power rule, , the coefficient a can be found by taking empirical measurements of run time <math>\{t_1, t_2\}</math> at some problem-size points <math>\{n_1, n_2\}</math>, and calculating <math>t_2/t_1 = (n_2/n_1)^a</math> so that <math>a = \log(t_2/t_1) / \log(n_2/n_1)</math>. In other words, this measures the slope of the empirical line on the log–log plot of execution time vs. problem size, at some size point. If the order of growth indeed follows the power rule (and so the line on log–log plot is indeed a straight line), the empirical value of a will stay constant at different ranges, and if not, it will change (and the line is a curved line) - but still could serve for comparison of any two given algorithms as to their empirical local orders of growth behaviour. Applied to the above table:
假设执行时间服从幂规则，系数 a 可以通过对运行时数学 t1，t2 / math 在某些问题大小点上的数学 n1，n2 / math 进行经验测量，然后计算数学 t2 / t1(n2 / n1) ^ a / math，从而得到数学 a / log (t2 / t1) / log (n2 / n1) / math。换句话说，在某个尺寸点上，这可以度量执行时间与问题大小的对数-对数图上经验曲线的斜率。如果增长的次序确实遵循幂次规则(因此对数曲线确实是一条直线) ，那么 a 的经验值将在不同的范围内保持不变，如果不是，它将发生变化(而且这条直线是一条曲线)——但仍然可以用于比较任何两个给定算法的经验局部增长行为次序。应用于上表:
{| class="wikitable"
{| class="wikitable"
{ | class“ wikitable”
|-_
|-_
|-_
! ''n'' (list size)
! n (list size)
!N (列表大小)
! Computer A run-time<br />(in [[nanosecond]]s)
! Computer A run-time<br />(in nanoseconds)
!运行时 br / (以纳秒为单位)
! Local order of growth<br />(n^_)
! Local order of growth<br />(n^_)
!生长 br / (n ^)的局部序
! Computer B run-time<br />(in [[nanosecond]]s)
! Computer B run-time<br />(in nanoseconds)
!计算机 b 运行时 br / (以纳秒为单位)
! Local order of growth<br />(n^_)
! Local order of growth<br />(n^_)
!生长 br / (n ^)的局部序
|-
|-
|-
| 15
| 15
| 15
| 7
| 7
| 7
|
|
|
| 100,000
| 100,000
| 100,000
|
|
|
|-
|-
|-
| 65
| 65
| 65
| 32
| 32
| 32
| 1.04
| 1.04
| 1.04
| 150,000
| 150,000
| 150,000
| 0.28
| 0.28
| 0.28
|-
|-
|-
| 250
| 250
| 250
| 125
| 125
| 125
| 1.01
| 1.01
| 1.01
| 200,000
| 200,000
| 200,000
| 0.21
| 0.21
| 0.21
|-
|-
|-
| 1,000
| 1,000
| 1,000
| 500
| 500
| 500
| 1.00
| 1.00
| 1.00
| 250,000
| 250,000
| 250,000
| 0.16
| 0.16
| 0.16
|-
|-
|-
| ...
| ...
| ...
| ...
| ...
| ...
|
|
|
| ...
| ...
| ...
|
|
|
|-
|-
|-
| 1,000,000
| 1,000,000
| 1,000,000
| 500,000
| 500,000
| 500,000
| 1.00
| 1.00
| 1.00
| 500,000
| 500,000
| 500,000
| 0.10
| 0.10
| 0.10
|-
|-
|-
| 4,000,000
| 4,000,000
| 4,000,000
| 2,000,000
| 2,000,000
| 2,000,000
| 1.00
| 1.00
| 1.00
| 550,000
| 550,000
| 550,000
| 0.07
| 0.07
| 0.07
|-
|-
|-
| 16,000,000
| 16,000,000
| 16,000,000
| 8,000,000
| 8,000,000
| 8,000,000
| 1.00
| 1.00
| 1.00
| 600,000
| 600,000
| 600,000
| 0.06
| 0.06
| 0.06
|-
|-
|-
| ...
| ...
| ...
| ...
| ...
| ...
|
|
|
| ...
| ...
| ...
|
|
|
|}
|}
|}
It is clearly seen that the first algorithm exhibits a linear order of growth indeed following the power rule. The empirical values for the second one are diminishing rapidly, suggesting it follows another rule of growth and in any case has much lower local orders of growth (and improving further still), empirically, than the first one.
It is clearly seen that the first algorithm exhibits a linear order of growth indeed following the power rule. The empirical values for the second one are diminishing rapidly, suggesting it follows another rule of growth and in any case has much lower local orders of growth (and improving further still), empirically, than the first one.
可以清楚地看到，第一个算法展示了一个线性增长序列，确实遵循幂规则。第二个经验值正在迅速递减，这表明它遵循了另一条增长规律，而且无论如何，从经验上看，当地的增长订单(以及进一步的增长)远低于第一个。
=== Evaluating run-time complexity ===
The run-time complexity for the worst-case scenario of a given algorithm can sometimes be evaluated by examining the structure of the algorithm and making some simplifying assumptions. Consider the following [[pseudocode]]:
The run-time complexity for the worst-case scenario of a given algorithm can sometimes be evaluated by examining the structure of the algorithm and making some simplifying assumptions. Consider the following pseudocode:
给定算法的运行绝境求生手册复杂度有时可以通过检查算法的结构和做一些简化的假设来评估。考虑下面的伪代码:
1 ''get a positive integer n from input''
1 get a positive integer n from input
1从输入得到一个正整数 n
2 '''if''' n > 10
2 if n > 10
2 if n 10
3 '''print''' "This might take a while..."
3 print "This might take a while..."
“这可能需要一段时间... ... ”
4 '''for''' i = 1 '''to''' n
4 for i = 1 to n
4表示 i 1到 n
5 '''for''' j = 1 '''to''' i
5 for j = 1 to i
5表示 j1表示 i
6 '''print''' i * j
6 print i * j
6 print i * j
7 '''print''' "Done!"
7 print "Done!"
打印7页“完成! ”
A given computer will take a [[DTIME|discrete amount of time]] to execute each of the [[Instruction (computer science)|instructions]] involved with carrying out this algorithm. The specific amount of time to carry out a given instruction will vary depending on which instruction is being executed and which computer is executing it, but on a conventional computer, this amount will be [[Deterministic system (mathematics)|deterministic]].<ref>However, this is not the case with a [[quantum computer]]</ref> Say that the actions carried out in step 1 are considered to consume time ''T''<sub>1</sub>, step 2 uses time ''T''<sub>2</sub>, and so forth.
A given computer will take a discrete amount of time to execute each of the instructions involved with carrying out this algorithm. The specific amount of time to carry out a given instruction will vary depending on which instruction is being executed and which computer is executing it, but on a conventional computer, this amount will be deterministic. Say that the actions carried out in step 1 are considered to consume time T<sub>1</sub>, step 2 uses time T<sub>2</sub>, and so forth.
给定的计算机将采取一个离散的时间量来执行与执行这个算法有关的每一个指令。执行给定指令的具体时间量取决于正在执行的指令和正在执行的计算机，但在传统计算机上，这个时间量是确定的。假设步骤1中执行的动作被认为消耗时间 t 子1 / 子，步骤2使用时间 t 子2 / 子，等等。
In the algorithm above, steps 1, 2 and 7 will only be run once. For a worst-case evaluation, it should be assumed that step 3 will be run as well. Thus the total amount of time to run steps 1-3 and step 7 is:
In the algorithm above, steps 1, 2 and 7 will only be run once. For a worst-case evaluation, it should be assumed that step 3 will be run as well. Thus the total amount of time to run steps 1-3 and step 7 is:
在上面的算法中，步骤1、2和7只运行一次。对于最坏情况的评估，应该假定步骤3也将运行。因此，运行步骤1-3和步骤7所需的总时间是:
:<math>T_1 + T_2 + T_3 + T_7. \,</math>
<math>T_1 + T_2 + T_3 + T_7. \,</math>
数学 t1 + t2 + t3 + t7。数学
The [[program loop|loops]] in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( ''n'' + 1 )
The loops in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( n + 1 )
步骤4、5和6中的循环更难计算。步骤4中的外部循环测试将执行(n + 1)
times (note that an extra step is required to terminate the for loop, hence n + 1 and not n executions), which will consume ''T''<sub>4</sub>( ''n'' + 1 ) time. The inner loop, on the other hand, is governed by the value of j, which [[iteration|iterates]] from 1 to ''i''. On the first pass through the outer loop, j iterates from 1 to 1: The inner loop makes one pass, so running the inner loop body (step 6) consumes ''T''<sub>6</sub> time, and the inner loop test (step 5) consumes 2''T''<sub>5</sub> time. During the next pass through the outer loop, j iterates from 1 to 2: the inner loop makes two passes, so running the inner loop body (step 6) consumes 2''T''<sub>6</sub> time, and the inner loop test (step 5) consumes 3''T''<sub>5</sub> time.
times (note that an extra step is required to terminate the for loop, hence n + 1 and not n executions), which will consume T<sub>4</sub>( n + 1 ) time. The inner loop, on the other hand, is governed by the value of j, which iterates from 1 to i. On the first pass through the outer loop, j iterates from 1 to 1: The inner loop makes one pass, so running the inner loop body (step 6) consumes T<sub>6</sub> time, and the inner loop test (step 5) consumes 2T<sub>5</sub> time. During the next pass through the outer loop, j iterates from 1 to 2: the inner loop makes two passes, so running the inner loop body (step 6) consumes 2T<sub>6</sub> time, and the inner loop test (step 5) consumes 3T<sub>5</sub> time.
时(注意，终止 for 循环需要一个额外的步骤，因此 n + 1而不是 n 次执行) ，这将消耗 t 小于4 / sub (n + 1)的时间。另一方面，内部循环由 j 的值控制，该值从1迭代到 i。在第一次通过外部循环时，j 迭代1到1: 内部循环通过一次，因此运行内部循环体(第6步)消耗 t 小于6 / 子时间，而内部循环测试(第5步)消耗2T 小于5 / 子时间。在下一次通过外部循环时，j 从1到2迭代: 内部循环进行两次通过，因此运行内部循环体(步骤6)消耗2T 子6 / 子时间，而内部循环测试(步骤5)消耗3T 子5 / 子时间。
Altogether, the total time required to run the inner loop body can be expressed as an [[arithmetic progression]]:
Altogether, the total time required to run the inner loop body can be expressed as an arithmetic progression:
总之，运行内部循环体所需的总时间可以用等差数列表示:
:<math>T_6 + 2T_6 + 3T_6 + \cdots + (n-1) T_6 + n T_6</math>
<math>T_6 + 2T_6 + 3T_6 + \cdots + (n-1) T_6 + n T_6</math>
数学 t6 + 2t6 + 3t6 + cdots + (n-1) t6 + n t6 / math
which can be [[factorization|factored]]<ref>It can be proven by [[Mathematical induction|induction]] that <math>1 + 2 + 3 + \cdots + (n-1) + n = \frac{n(n+1)}{2}</math></ref> as
which can be factored as
这可以作为一个因素
:<math>T_6 \left[ 1 + 2 + 3 + \cdots + (n-1) + n \right] = T_6 \left[ \frac{1}{2} (n^2 + n) \right] </math>
<math>T_6 \left[ 1 + 2 + 3 + \cdots + (n-1) + n \right] = T_6 \left[ \frac{1}{2} (n^2 + n) \right] </math>
数学 t6左[1 + 2 + 3 + cdots + (n-1) + n 右] t6左[ frac {1}{2}(n ^ 2 + n)右] / 数学
The total time required to run the outer loop test can be evaluated similarly:
The total time required to run the outer loop test can be evaluated similarly:
运行外部循环测试所需的总时间可以用类似的方法计算:
:<math>\begin{align}
<math>\begin{align}
数学 begin { align }
& 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1) T_5 + n T_5 + (n + 1) T_5\\
& 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1) T_5 + n T_5 + (n + 1) T_5\\
2t5 + 3t5 + 4t5 + cdots + (n-1) t5 + n t5 + (n + 1) t5
=\ &T_5 + 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1)T_5 + nT_5 + (n+1)T_5 - T_5
=\ &T_5 + 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1)T_5 + nT_5 + (n+1)T_5 - T_5
5 + 2t5 + 3t5 + 4t5 + cdots + (n-1) t5 + nT 5 + (n + 1) t5-t5
\end{align}</math>
\end{align}</math>
End { align } / math
which can be factored as
which can be factored as
这可以作为一个因素
:<math>\begin{align}
<math>\begin{align}
数学 begin { align }
& T_5 \left[ 1+2+3+\cdots + (n-1) + n + (n + 1) \right] - T_5 \\
& T_5 \left[ 1+2+3+\cdots + (n-1) + n + (n + 1) \right] - T_5 \\
& t5左[1 + 2 + 3 + cdots + (n-1) + n + (n + 1)右]-t5
=& \left[ \frac{1}{2} (n^2 + n) \right] T_5 + (n + 1)T_5 - T_5 \\
=& \left[ \frac{1}{2} (n^2 + n) \right] T_5 + (n + 1)T_5 - T_5 \\
左[ frac {1}{2}(n ^ 2 + n)右] t5 + (n + 1) t5-t5
=& T_5 \left[ \frac{1}{2} (n^2 + n) \right] + n T_5 \\
=& T_5 \left[ \frac{1}{2} (n^2 + n) \right] + n T_5 \\
& t 5左[ frac {1}{2}(n ^ 2 + n)右] + n t 5
=& \left[ \frac{1}{2} (n^2 + 3n) \right] T_5
=& \left[ \frac{1}{2} (n^2 + 3n) \right] T_5
左[ frac {1}{2}(n ^ 2 + 3n)右] t 5
\end{align}</math>
\end{align}</math>
End { align } / math
Therefore, the total running time for this algorithm is:
Therefore, the total running time for this algorithm is:
因此，此算法的总运行时间为:
:<math>f(n) = T_1 + T_2 + T_3 + T_7 + (n + 1)T_4 + \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2+3n) \right] T_5 </math>
<math>f(n) = T_1 + T_2 + T_3 + T_7 + (n + 1)T_4 + \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2+3n) \right] T_5 </math>
数学 f (n) t1 + t2 + t3 + t7 + (n + 1) t4 + 左[ frac {1}(n ^ 2 + n)右] t6 + 左[ frac {1}(n ^ 2 + 3 n)右] t5 / math
which [[reduction (mathematics)|reduces]] to
which reduces to
这就简化为
:<math>f(n) = \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7
<math>f(n) = \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7
数学 f (n)左[ frac {1}{2}(n ^ 2 + n)右] t6 + 左[ frac {1}(n ^ 2 + 3n)右] t5 + (n + 1) t4 + t1 + t2 + t3 + t7
</math>
</math>
数学
As a [[rule-of-thumb]], one can assume that the highest-order term in any given function dominates its rate of growth and thus defines its run-time order. In this example, n<sup>2</sup> is the highest-order term, so one can conclude that f(n) = O(n<sup>2</sup>). Formally this can be proven as follows:
As a rule-of-thumb, one can assume that the highest-order term in any given function dominates its rate of growth and thus defines its run-time order. In this example, n<sup>2</sup> is the highest-order term, so one can conclude that f(n) = O(n<sup>2</sup>). Formally this can be proven as follows:
作为一个经验法则，我们可以假设任何给定函数中的最高阶项主导了它的增长率，从而定义了它的运行时序。在这个例子中，n sup 2 / sup 是最高阶项，因此可以得出 f (n) o (n sup 2 / sup)。在形式上，这可以证明如下:
{{quote|Prove that <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2,\ n \ge n_0</math>
{{quote|Prove that <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2,\ n \ge n_0</math>
{引号 | 证明数学左[ frac {1}{2}(n ^ 2 + n)右] t6 + 左[ frac {1}(n ^ 2 + 3n)右] t5 + (n + 1) t4 + t1 + t2 + t3 + t7 cn ^ 2， n ge n0 / math
<br /><br />
<br /><br />
Br / br /
<math>\begin{align}
<math>\begin{align}
数学 begin { align }
&\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7\\
&\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7\\
左[ frac {1}{2}(n ^ 2 + n)右] t6 + 左[ frac {1}{2}(n ^ 2 + 3n)右] t5 + (n + 1) t4 + t1 + t2 + t3 + t7
\le &( n^2 + n )T_6 + ( n^2 + 3n )T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \ (\text{for } n \ge 0 )
\le &( n^2 + n )T_6 + ( n^2 + 3n )T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \ (\text{for } n \ge 0 )
(n ^ 2 + n) t6 + (n ^ 2 + 3n) t5 + (n + 1) t4 + t1 + t2 + t3 + t7(for } n ge0)
\end{align}</math>
\end{align}</math>
End { align } / math
<br /><br />
<br /><br />
Br / br /
Let ''k'' be a constant greater than or equal to [''T''<sub>1</sub>..''T''<sub>7</sub>]
Let k be a constant greater than or equal to [T<sub>1</sub>..T<sub>7</sub>]
设 k 为大于或等于[ t 小于1 / 小于. . t 小于7 / 小于]的常数
<br /><br />
<br /><br />
Br / br /
<math>\begin{align}
<math>\begin{align}
数学 begin { align }
&T_6( n^2 + n ) + T_5( n^2 + 3n ) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k( n^2 + n ) + k( n^2 + 3n ) + kn + 5k\\
&T_6( n^2 + n ) + T_5( n^2 + 3n ) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k( n^2 + n ) + k( n^2 + 3n ) + kn + 5k\\
& t6(n ^ 2 + n) + t5(n ^ 2 + 3n) + (n + 1) t4 + t1 + t2 + t3 + t7 le k (n ^ 2 + n) + k (n ^ 2 + 3n) + kn + 5k
= &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
= &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
= &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
\end{align}</math>
\end{align}</math>
End { align } / math
<br /><br />
<br /><br />
Br / br /
Therefore <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2, n \ge n_0 \text{ for } c = 12k, n_0 = 1</math>
Therefore <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2, n \ge n_0 \text{ for } c = 12k, n_0 = 1</math>
因此，数学左[ frac {1}{2}(n ^ 2 + n)右] t6 + 左[ frac {1}(n ^ 2 + 3n)右] t5 + (n + 1) t4 + t1 + t2 + t3 + t7 le ^ cn 2，n ge n 0 text { for } c12k，n 01 / math
}}
}}
}}
A more [[elegance|elegant]] approach to analyzing this algorithm would be to declare that [''T''<sub>1</sub>..''T''<sub>7</sub>] are all equal to one unit of time, in a system of units chosen so that one unit is greater than or equal to the actual times for these steps. This would mean that the algorithm's running time breaks down as follows:<ref>This approach, unlike the above approach, neglects the constant time consumed by the loop tests which terminate their respective loops, but it is [[Trivial (mathematics)|trivial]] to prove that such omission does not affect the final result</ref>
A more elegant approach to analyzing this algorithm would be to declare that [T<sub>1</sub>..T<sub>7</sub>] are all equal to one unit of time, in a system of units chosen so that one unit is greater than or equal to the actual times for these steps. This would mean that the algorithm's running time breaks down as follows:
分析此算法的一个更优雅的方法是声明[ t 子1 / sub。 . T 小于7 / sub ]都等于一个时间单位，在一个选择的单位系统中，一个单位大于或等于这些步骤的实际时间。这意味着该算法的运行时间分解如下:
{{quote|<math>4+\sum_{i=1}^n i\leq 4+\sum_{i=1}^n n=4+n^2\leq5n^2 \ (\text{for } n \ge 1) =O(n^2).</math>}}
===Growth rate analysis of other resources===
The methodology of run-time analysis can also be utilized for predicting other growth rates, such as consumption of [[DSPACE|memory space]]. As an example, consider the following pseudocode which manages and reallocates memory usage by a program based on the size of a [[computer file|file]] which that program manages:
The methodology of run-time analysis can also be utilized for predicting other growth rates, such as consumption of memory space. As an example, consider the following pseudocode which manages and reallocates memory usage by a program based on the size of a file which that program manages:
运行时分析的方法也可用于预测其他增长率，如内存空间的消耗。例如，考虑下面的伪代码，它根据程序管理的文件的大小来管理和重新分配程序的内存使用:
'''while''' ''file is still open:''
while file is still open:
在文件还开着的时候:
'''let''' n = ''size of file''
let n = size of file
文件大小 n
'''for''' ''every 100,000 [[kilobyte]]s of increase in file size''
for every 100,000 kilobytes of increase in file size
文件大小每增加10万千字节
''double the amount of memory reserved''
double the amount of memory reserved
保留的内存量翻倍
In this instance, as the file size n increases, memory will be consumed at an [[exponential growth]] rate, which is order O(2<sup>n</sup>). This is an extremely rapid and most likely unmanageable growth rate for consumption of memory [[Resource (computer science)|resources]].
In this instance, as the file size n increases, memory will be consumed at an exponential growth rate, which is order O(2<sup>n</sup>). This is an extremely rapid and most likely unmanageable growth rate for consumption of memory resources.
在这个例子中，随着文件大小 n 的增加，内存消耗的速度将达到指数增长，即 o (2 sup n / sup)。对于内存资源的消耗，这是一个极其快速且最有可能无法控制的增长率。
==Relevance==
Algorithm analysis is important in practice because the accidental or unintentional use of an inefficient algorithm can significantly impact system performance. In time-sensitive applications, an algorithm taking too long to run can render its results outdated or useless. An inefficient algorithm can also end up requiring an uneconomical amount of computing power or storage in order to run, again rendering it practically useless.
Algorithm analysis is important in practice because the accidental or unintentional use of an inefficient algorithm can significantly impact system performance. In time-sensitive applications, an algorithm taking too long to run can render its results outdated or useless. An inefficient algorithm can also end up requiring an uneconomical amount of computing power or storage in order to run, again rendering it practically useless.
算法分析在实践中非常重要，因为偶然或无意地使用低效算法会显著影响系统性能。在对时间敏感的应用程序中，运行时间过长的算法可能使其结果过时或无用。一个低效的算法也可能最终需要不经济的计算能力或存储量才能运行，再一次使它变得毫无用处。
==Constant factors==
Analysis of algorithms typically focuses on the asymptotic performance, particularly at the elementary level, but in practical applications constant factors are important, and real-world data is in practice always limited in size. The limit is typically the size of addressable memory, so on 32-bit machines 2<sup>32</sup> = 4 GiB (greater if [[segmented memory]] is used) and on 64-bit machines 2<sup>64</sup> = 16 EiB. Thus given a limited size, an order of growth (time or space) can be replaced by a constant factor, and in this sense all practical algorithms are O(1) for a large enough constant, or for small enough data.
Analysis of algorithms typically focuses on the asymptotic performance, particularly at the elementary level, but in practical applications constant factors are important, and real-world data is in practice always limited in size. The limit is typically the size of addressable memory, so on 32-bit machines 2<sup>32</sup> = 4 GiB (greater if segmented memory is used) and on 64-bit machines 2<sup>64</sup> = 16 EiB. Thus given a limited size, an order of growth (time or space) can be replaced by a constant factor, and in this sense all practical algorithms are O(1) for a large enough constant, or for small enough data.
对算法的分析通常侧重于渐近性能，特别是在初级水平，但在实际应用中，常数因素是重要的，而实际数据在规模上总是有限的。这个限制通常是可寻址内存的大小，所以在32位机器2 sup 32 / sup 4gib (如果使用分段内存则更大)和64位机器2 sup 64 / sup 16 EiB 上。因此，给定一个有限的大小，一个增长的顺序(时间或空间)可以被一个常量因子所取代，在这个意义上，所有实用的算法对于足够大的常量或足够小的数据都是 o (1)。
This interpretation is primarily useful for functions that grow extremely slowly: (binary) [[iterated logarithm]] (log<sup>*</sup>) is less than 5 for all practical data (2<sup>65536</sup> bits); (binary) log-log (log log ''n'') is less than 6 for virtually all practical data (2<sup>64</sup> bits); and binary log (log ''n'') is less than 64 for virtually all practical data (2<sup>64</sup> bits). An algorithm with non-constant complexity may nonetheless be more efficient than an algorithm with constant complexity on practical data if the overhead of the constant time algorithm results in a larger constant factor, e.g., one may have <math>K > k \log \log n</math> so long as <math>K/k > 6</math> and <math>n < 2^{2^6} = 2^{64}</math>.
This interpretation is primarily useful for functions that grow extremely slowly: (binary) iterated logarithm (log<sup>*</sup>) is less than 5 for all practical data (2<sup>65536</sup> bits); (binary) log-log (log log n) is less than 6 for virtually all practical data (2<sup>64</sup> bits); and binary log (log n) is less than 64 for virtually all practical data (2<sup>64</sup> bits). An algorithm with non-constant complexity may nonetheless be more efficient than an algorithm with constant complexity on practical data if the overhead of the constant time algorithm results in a larger constant factor, e.g., one may have <math>K > k \log \log n</math> so long as <math>K/k > 6</math> and <math>n < 2^{2^6} = 2^{64}</math>.
这种解释主要适用于增长极其缓慢的函数: (二进制)迭代对数(log sup * / sup)对所有实际数据(2 sup 65536 / sup bit)小于5; (二进制) log-log (log n)对几乎所有实际数据(2 sup 64 / sup bit)小于6; 二进制 log (log n)对几乎所有实际数据(2 sup 64 / sup bits)小于64。如果常量时间算法的开销导致一个更大的常量因子，那么非常量复杂度的算法可能比实际数据上的常量复杂度算法更有效，例如，只要有数学 k / k6 / math 和数学 n2 ^ {2 ^ 6}2 ^ {64} / math，就可能有数学 k log n / math。
For large data linear or quadratic factors cannot be ignored, but for small data an asymptotically inefficient algorithm may be more efficient. This is particularly used in [[hybrid algorithm]]s, like [[Timsort]], which use an asymptotically efficient algorithm (here [[merge sort]], with time complexity <math>n \log n</math>), but switch to an asymptotically inefficient algorithm (here [[insertion sort]], with time complexity <math>n^2</math>) for small data, as the simpler algorithm is faster on small data.
For large data linear or quadratic factors cannot be ignored, but for small data an asymptotically inefficient algorithm may be more efficient. This is particularly used in hybrid algorithms, like Timsort, which use an asymptotically efficient algorithm (here merge sort, with time complexity <math>n \log n</math>), but switch to an asymptotically inefficient algorithm (here insertion sort, with time complexity <math>n^2</math>) for small data, as the simpler algorithm is faster on small data.
对于大数据不能忽略线性因子或二次因子，但对于小数据，渐近低效算法可能更有效。这在混合算法中尤其常用，比如 Timsort，它使用一种渐近有效的算法(在这里使用合并排序，时间复杂度数学 n log n / math) ，但是对于小数据切换到一种渐近低效的算法(在这里使用插入排序，时间复杂度数学 n ^ 2 / math) ，因为更简单的算法在小数据上更快。
==See also==
* [[Amortized analysis]]
* [[Analysis of parallel algorithms]]
* [[Asymptotic computational complexity]]
* [[Best, worst and average case]]
* [[Big O notation]]
* [[Computational complexity theory]]
* [[Master theorem (analysis of algorithms)]]
* [[NP-Complete]]
* [[Numerical analysis]]
* [[Polynomial time]]
* [[Program optimization]]
* [[Profiling (computer programming)]]
* [[Scalability]]
* [[Smoothed analysis]]
* [[Termination analysis]] — the subproblem of checking whether a program will terminate at all
* [[Time complexity]] — includes table of orders of growth for common algorithms
* [[Information-based complexity]]
==Notes==
{{reflist}}
==References==
*{{Cite book |authorlink=Thomas H. Cormen |first=Thomas H. |last=Cormen |authorlink2=Charles E. Leiserson |first2=Charles E. |last2=Leiserson |authorlink3=Ronald L. Rivest |first3=Ronald L. |last3=Rivest |lastauthoramp=yes |authorlink4=Clifford Stein |first4=Clifford |last4=Stein |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press and McGraw-Hill |location=Cambridge, MA |year=2001 |isbn=0-262-03293-7 |others=Chapter 1: Foundations |pages=3–122 }}
*{{Cite book |title=Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching |edition=3rd |authorlink=Robert Sedgewick (computer scientist) |first=Robert |last=Sedgewick |location=Reading, MA |publisher=Addison-Wesley Professional |year=1998 |isbn=978-0-201-31452-6 |url-access=registration |url=https://archive.org/details/algorithmsinc00sedg }}
*{{Cite book |title=[[The Art of Computer Programming]] |authorlink=Donald Knuth |first=Donald |last=Knuth |location= |publisher=Addison-Wesley |isbn= |year= }}
*{{Cite book |first=Daniel A. |last=Greene |first2=Donald E. |last2=Knuth |title=Mathematics for the Analysis of Algorithms |edition=Second |location= |publisher=Birkhäuser |year=1982 |isbn=3-7643-3102-X }}
*{{Cite book |authorlink=Oded Goldreich |first=Oded |last=Goldreich |title=Computational Complexity: A Conceptual Perspective |location= |publisher=[[Cambridge University Press]] |year=2010 |isbn=978-0-521-88473-0 }}
==External links==
*{{Commonscatinline}}
{{Computer science}}
{{DEFAULTSORT:Analysis Of Algorithms}}
[[Category:Analysis of algorithms| ]]
[[Category:Computational complexity theory]]
Category:Computational complexity theory
类别: 计算复杂性理论
<noinclude>
<small>This page was moved from [[wikipedia:en:Analysis of algorithms]]. Its edit history can be viewed at [[算法分析/edithistory]]</small></noinclude>
[[Category:待整理页面]]