7,129
个编辑
更改
跳到导航
跳到搜索
第100行：
第100行： − + + − 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. − − 由于算法是'''平台无关的 Platform-Independent'''（即一个给定的算法，可以在任意运行任意'''操作系统 Operating System'''的计算机上用任意'''编程语言 Programming Language'''实现），使用经验方法来衡量一组给定算法的比较性能还有一个明显的缺点。 − − − − 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: − − 举个例子，一个程序在一个大小为n的排序列表中查找一个特定的条目。假设这个程序是在A计算机上实现的，A计算机是最先进的机器，使用线性搜索算法，而B计算机使用二分法进行搜索，但是B计算机本身的运行速度要慢得多。两台计算机分别运行该程序的基准测试结果如下所示: 第165行：
第154行： − 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计算机。然而，如果输入列表的大小增加到一个足够大的数字，这个结论就会发生戏剧性的反转。 第261行：
第246行： − + + − 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，因为它运行的算法增长速度要慢得多。
→经验指标的缺陷 Shortcomings of empirical metrics
===经验指标的缺陷 Shortcomings of empirical metrics===
===经验指标的缺陷===
由于算法与平台无关（即一个给定的算法，可以在任意运行任意操作系统的计算机上用任意编程语言实现），使用经验方法来衡量一组给定算法的比较性能还有一个明显的缺点。
举个例子，一个程序在一个大小为''n''的排序列表中查找一个特定的条目。假设这个程序是在A计算机上实现的，计算机A是最先进的机器，使用线性搜索算法，而计算机B使用二分法进行搜索，但是B计算机本身的运行速度要慢得多。两台计算机分别运行该程序的基准测试结果如下所示:
基于这些度量，我们很容易得出结论：计算机A运行的算法在效率上远远优于计算机B。然而，如果输入列表的大小增加到一个足够大的数字，这个结论就会发生戏剧性的反转。
| 31,536 × 10<sup>12</sup> ns,<br />or 1 year
| 31,536 × 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 毫秒
|}
|}
运行线性搜索程序的计算机A的效率呈现线性增长，即程序的运行时间与其输入大小成正比，也就是说将输入大小增加一倍时运行时间也将增加一倍，将输入大小增加四倍则运行时间也会增加四倍等等。另一方面，运行二分法搜索程序的计算机B的效率呈现出对数增长趋势，将输入大小变成原来的两倍只会使运行时增加一个常量（在本例中为50,000 ns）。尽管从表面上看计算机A是一台速度更快的机器，但计算机B在运行时势必会地超过计算机A，因为它运行的算法增长速度要慢得多。
<br>
===生长规律===
===生长规律===