Analysis of algorithms: Difference between revisions
Jump to navigation
Jump to search
imported>Widefox m →See also: already in body per WP:SEEALSO / WP:OVERLINK |
imported>Jochen Burghardt →Empirical orders of growth: insert article; a is not a coefficient; set notation is wrong here; solve, not calculate |
||
| Line 115: | Line 115: | ||
===Empirical orders of growth=== | ===Empirical orders of growth=== | ||
Assuming the run-time follows power rule, {{math|''t'' ≈ ''kn''<sup>''a''</sup>}}, the | Assuming the run-time follows the power rule, {{math|''t'' ≈ ''kn''<sup>''a''</sup>}}, the parameter {{mvar|''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''<sub>1</sub>}} and {{math|''t''<sub>2</sub>}} at some problem-size points {{math|''n''<sub>1</sub>}} and {{math|''n''<sub>2</sub>}}, and solving the equation {{math|1=''t''<sub>2</sub>/''t''<sub>1</sub> = (''n''<sub>2</sub>/''n''<sub>1</sub>)<sup>''a''</sup>}} w.r.t. {{mvar|a}}, that is, {{math|1=''a'' = log(''t''<sub>2</sub>/''t''<sub>1</sub>)/log(''n''<sub>2</sub>/''n''<sub>1</sub>)}}. In other words, this measures the slope of the empirical line on the [[log–log plot]] of run-time vs. input size, at some size point. If the order of growth indeed follows the power rule (and so the line on the log–log plot is indeed a straight line), the empirical value of {{mvar|a}} will stay constant at different ranges, and if not, it will change (and the line is a curved line)—but still can serve for comparison of any two given algorithms as to their ''empirical local orders of growth'' behaviour. Applied to the above table: | ||
{| class="wikitable" | {| class="wikitable" | ||