Granda O: Malsamoj inter versioj
| [nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
Boehm (diskuto | kontribuoj) e →Propraĵoj: typog |
|||
Linio 159:
Por ''c>1'', ''O(n<sup>c</sup>)'' kaj ''O(c<sup>n</sup>)'' estas tre malsamaj. La lasta kreskas multe, multe pli rapida, sendepende de la konstanto ''c'' estas (se ĝi estas pli granda ol unu). Funkcio kiu kreskas pli rapida ol ĉiu potenco de ''n'' estas ''superpolinoma''. Funkcio kiu kreskas pli malrapide ol ĉiu eksponenta funkcio de formo <math>c^n</math> estas ''subeksponenta''. Funkcio povas esti ambaŭ superpolinoma kaj subeksponenta. Ekzemple ĉi tia estas tempo de [[ĝenerala nombra kampa kribrilo]], la plej rapida sciata algoritmo por [[entjera faktorigo]], kiu por ''b''-bita nombro estas:
:<math>O\left(\exp\left(\left(\frac{64b}{9}\right)^{1\over3} (\log b)^{2\over3}\right)\right).</math>
''O(log(n<sup>c</sup>))'' estas akurate la samo kiel ''O(log n)''. La logaritmoj diferenciĝas nur per konstanta faktoro pro tio ke ''log(n<sup>c</sup>)=c log n'' kaj tial la granda ''O'' ignoras la diferencon. Simile logaritmoj kun malsamaj konstantaj bazoj estas ekvivalentaj. Eksponentoj kun malsamaj bazoj, male, estas ne de la sama ordo. Ekzemple, ''2<sup>n</sup>'' kaj ''3<sup>n</sup>'' estas ne de la sama ordo.
| |||