Produto de lineara kaj logaritma funkcio

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) aŭ o(n^1+ε) 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:

• Rapida ordigo nur en la averaĝa okazo
• Piramida ordigo, kunfanda ordigo, duuma arba ordigo, paciencluda ordigo kaj tiel plu en la plej malbona okazo
• Rapida konverto de Fourier