| 第214行： |
第214行： |
| | <br> | | <br> |
| | | | |
| − | ===经验增长规律 Empirical orders of growth=== | + | ===经验增长规律 === |
| | | | |
| − | | + | 假设算法运行时间遵循幂律规则，''{{math|t ≈ k n<sup>a</sup>}}''，系数''a''可以通过对一些问题规模点<math>\{n_1, n_2\}</math>的运行时间<math>\{t_1, t_2\}</math>进行经验测量，并计算出𝑡<math>t_2/t_1 = (n_2/n_1)^a</math>，从而得到系数<math>a = \log(t_2/t_1) / \log(n_2/n_1)</math>。 |
| − | | + | 换言之，这衡量了在某个规模点上，执行时间与问题大小的双对数曲线 log-log plot上经验线的斜率。如果增长顺序确实遵循幂律（因此双对数曲线图上的直线确实是一条直线），那么a的经验值将在不同的范围内将保持不变，如果不是，它将发生改变（而且这条线是一条曲线），但仍然可以用来比较任何两种给定算法的经验局部增长顺序。应用于下表： |
| − | 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:
| |
| − | | |
| − | 假设算法运行时间遵循幂律规则，''{{math|t ≈ k n<sup>a</sup>}}''，通过对一些问题规模点<math>\{n_1, n_2\}</math>的运行时间<math>\{t_1, t_2\}</math>进行经验测量，并计算出𝑡<math>t_2/t_1 = (n_2/n_1)^a</math>，从而得到系数<math>a = \log(t_2/t_1) / \log(n_2/n_1)</math>。
| |
| − | 换言之，这衡量了在某个规模点上，执行时间与问题大小的双对数曲线 log-log plot上经验线的斜率。如果增长顺序确实遵循幂律（因此双对数曲线图上的直线确实是一条直线），那么a的经验值将在不同的范围内将保持不变，如果不是，它将发生改变（而且这条线是一条曲线），但仍然可以用来比较任何两种给定算法的经验局部增长顺序。应用于上表： | |
| | | | |
| | | | |