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(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:
- 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
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
