Metraipolis › archive › dc_83eae367be71

Notazione L — Wikipedia

Source: Wikipedia (it)
Original: https://it.wikipedia.org/wiki/Notazione_L
License (as archived): CC-BY-SA-4.0
Archived: 2026-11-07T23:51:17.230Z
SHA-256 of the archived text: 19453c232807050fa4a1dc74a4c495c60019eb862fec73b46067f18bd5b3dd68
Stable URL of this page: https://metraipolis.com/documento/dc_83eae367be71

How to cite

Notazione L — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Notazione_L (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_83eae367be71 (Metraipolis archive dc_83eae367be71, sha256 19453c232807050fa4a1dc74a4c495c60019eb862fec73b46067f18bd5b3dd68)

BibTeX

@misc{dc83eae367be71,
  title = {Notazione L — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Notazione_L},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_83eae367be71; sha256 19453c232807050fa4a1dc74a4c495c60019eb862fec73b46067f18bd5b3dd68},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Notazione_L. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

La notazione L è una notazione asintotica analoga alla notazione O-grande, denotata come L n [ α , c ] {\displaystyle L_{n}[\alpha ,c]} per una variabile limitata n {\displaystyle n} tendente a infinito. Come la notazione O-grande, è usata di solito per rendere in maniera approssimativa la complessità computazionale di un particolare algoritmo. Essa è definita come L n [ α , c ] = e ( c + o ( 1 ) ) ( ln n ) α ( ln ln n ) 1 − α , {\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},} dove c è una costante positiva, e α {\displaystyle \alpha } è una costante 0 ≤ α ≤ 1 {\displaystyle 0\leq \alpha \leq 1} . La notazione L si usa principalmente nella teoria computazionale dei numeri, per esprimere la complessità degli algoritmi per i problemi difficili della teoria dei numeri, ad es. per la fattorizzazione degli interi e per i metodi di soluzione dei logaritmi discreti. Il beneficio di questa notazione è che semplifica l'analisi di questi logaritmi. La e c ( ln n ) α ( ln ln n ) 1 − α {\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}} esprime il termine dominante, e la e o ( 1 ) ( ln n ) α ( ln ln n ) 1 − α {\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}} copre tutto ciò che è minore. Quando α {\displaystyle \alpha } è 0, allora L n [ α , c ] = L n [ 0 , c ] = e ( c + o ( 1 ) ) ln ln n = ( ln n ) c + o ( 1 ) {\displaystyle L_{n}[\alpha ,c]=L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}\,} è una funzione polinomiale di ln n; quando α {\displaystyle \alpha } è 1, allora L n [ α , c ] = L n [ 1 , c ] = e ( c + o ( 1 ) ) ln n = n c + o ( 1 ) {\displaystyle L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}\,} è una funzione completamente esponenziale di ln n (e quindi polinomiale in n). Se α {\displaystyle \alpha } è compreso tra 0 e 1, la funzione è subesponenziale (e superpolinomiale).

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Notazione L» — https://it.wikipedia.org/wiki/Notazione_L
Wikidata Q15401695: «notation describing limiting behavior in computational number theory» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q15401695
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Notazione_L?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 148249507, consultata il 2026-11-07T23:46:14.476Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 487b6f2042ec47893876fe6e346281fb1790d276ecf749afbdd56c8cb9262db7