Content deleted Content added
m Open access bot: hdl added to citation with #oabot. |
Mytochondria (talk | contribs) →Efficient average-case complexity: Formatting fix Tags: Mobile edit Mobile web edit |
||
Line 17:
===Efficient average-case complexity===
The first task is to precisely define what is meant by an algorithm which is efficient "on average". An initial attempt might define an efficient average-case algorithm as one which runs in expected polynomial time over all possible inputs. Such a definition has various shortcomings; in particular, it is not robust to changes in the computational model. For example, suppose algorithm A runs in time t<sub>A</sub>(x) on input x and algorithm B runs in time t<sub>A</sub>(x)<sup>2</sup> on input x; that is, B is quadratically slower than A. Intuitively, any definition of average-case efficiency should capture the idea that A is efficient-on-average if and only if B is efficient on-average. Suppose, however, that the inputs are drawn randomly from the uniform distribution of strings with length <math>n</math>, and that A runs in time n<sup>2</sup> on all inputs except the string 1<sup>n</sup> for which A takes time 2<sup>n</sup>. Then it can be easily checked that the expected running time of A is polynomial but the expected running time of B is exponential.<ref name="bog06" />
To create a more robust definition of average-case efficiency, it makes sense to allow an algorithm A to run longer than polynomial time on some inputs but the fraction of inputs on which A requires larger and larger running time becomes smaller and smaller. This intuition is captured in the following formula for average polynomial running time, which balances the polynomial trade-off between running time and fraction of inputs:
| |||