Produto de lineara kaj logaritma funkcio

El Vikipedio, la libera enciklopedio
(Alidirektita el N log n)
Saltu al: navigado, serĉo

En matematiko, produto de lineara kaj logaritma funkcio estas funkcio de formo n · log n, kio estas, produto de lineara kaj logaritma partoj.

Laŭ la ordo de kresko, produto de lineara kaj logaritma estas ω(n)o(n1+ε) por ĉiu ε > 0, kaj Θ(n · log n). Tial, produto de lineara kaj logaritma eroj kreskas pli rapide ol lineara funkcio sed pli malrapida ol kvadrata funkcio.

Komparo (ordigo) postulas almenaŭ produtan de lineara kaj logaritma kvanton de komparoj en la plej malbona okazo ĉar

log(n!) = Θ(n log n)

Produto de lineara kaj logaritma funkcio ankaŭ ofte aperas de la rekursieca rilato

T(n) = 2 T(n / 2) + O(n)

Iuj algoritmoj kiuj ruliĝas en produta de lineara kaj logaritma tempo estas: