Domanda Cosa significa esattamente O (log n)?


Attualmente sto imparando i tempi di esecuzione di Big O Notation e i tempi ammortizzati. Capisco la nozione di Sopra) tempo lineare, nel senso che la dimensione dell'ingresso influisce sulla crescita dell'algoritmo proporzionalmente ... e lo stesso vale, ad esempio, per il tempo quadratico Sopra2) ecc. anche algoritmi, come i generatori di permutazione, con Sopra!) tempi, che crescono per fattori.

Ad esempio, la seguente funzione è Sopra) perché l'algoritmo cresce in proporzione al suo input n:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Allo stesso modo, se ci fosse un ciclo annidato, il tempo sarebbe O (n2).

Ma cosa è esattamente O (log n)? Ad esempio, cosa significa dire che l'altezza di un albero binario completo è O (log n)?

So (forse non in modo molto dettagliato) che cos'è Logarithm, nel senso che: log10 100 = 2, ma non riesco a capire come identificare una funzione con un tempo logaritmico.


1732
2018-02-21 20:05


origine


risposte:


Non riesco a capire come identificare una funzione con un tempo di registro.

Gli attributi più comuni della funzione di runtime logaritmico sono:

  • la scelta dell'elemento successivo su cui eseguire un'azione è una delle varie possibilità, e
  • solo uno dovrà essere scelto.

o

  • gli elementi su cui viene eseguita l'azione sono cifre di n

Questo è il motivo per cui, ad esempio, cercare persone in una rubrica è O (log n). Non è necessario controllare ogni persona nella rubrica per trovare quella giusta; invece, puoi semplicemente dividere e conquistare guardando in base a dove il loro nome è in ordine alfabetico, e in ogni sezione devi solo esplorare un sottoinsieme di ogni sezione prima di trovare il numero di telefono di qualcuno.

Ovviamente, una rubrica più grande ti richiederà ancora più tempo, ma non aumenterà altrettanto rapidamente quanto l'aumento proporzionale delle dimensioni aggiuntive.


Possiamo espandere l'esempio della rubrica per confrontare altri tipi di operazioni e loro tempo di esecuzione. Assumeremo che la nostra rubrica telefonica abbia aziende (le "Pagine Gialle") che hanno nomi univoci e persone (le "Pagine Bianche") che potrebbero non avere nomi univoci. Un numero di telefono è assegnato al massimo a una persona o azienda. Assumeremo anche che ci vuole tempo costante per lanciarsi su una pagina specifica.

Ecco i tempi di esecuzione di alcune operazioni che potremmo eseguire sulla rubrica, dal meglio al peggio:

  • O (1) (best case): Data la pagina in cui si trova il nome di un'azienda e il nome dell'azienda, trova il numero di telefono.

  • O (1) (caso medio): Data la pagina in cui si trova il nome di una persona e il suo nome, trova il numero di telefono.

  • O (log n): Dato il nome di una persona, trova il numero di telefono selezionando un punto casuale a metà della parte del libro che non hai ancora cercato, quindi verifica se il nome della persona è a quel punto. Quindi ripeti il ​​processo a metà della parte del libro in cui si trova il nome della persona. (Questa è una ricerca binaria per il nome di una persona.)

  • Sopra): Trova tutte le persone i cui numeri di telefono contengano la cifra "5".

  • Sopra): Dato un numero di telefono, trova la persona o l'azienda con quel numero.

  • O (n log n): C'era una confusione nell'ufficio della stampante e la nostra rubrica telefonica aveva inserito tutte le sue pagine in un ordine casuale. Correggere l'ordine in modo che sia corretto osservando il nome di ogni pagina e quindi inserendo la pagina nel punto appropriato in una nuova rubrica vuota.

Per gli esempi di seguito, siamo ora presso l'ufficio della stampante. Le rubriche telefoniche sono in attesa di essere spedite per posta a ciascun residente o azienda, e su ogni rubrica telefonica è presente un'etichetta che indica dove deve essere inviata la posta. Ogni persona o azienda riceve una rubrica.

  • O (n log n): Vogliamo personalizzare l'elenco telefonico, quindi troveremo il nome di ogni persona o azienda nella copia designata, quindi cercheremo il loro nome nel libro e scriveremo una breve nota di ringraziamento per il loro patrocinio.

  • Sopra2): Si è verificato un errore in ufficio e ogni voce in ciascuna rubrica ha uno "0" in più alla fine del numero di telefono. Prendi un po 'di bianco e rimuovi ogni zero.

  • O (n · n!): Siamo pronti per caricare le rubriche sul dock di spedizione. Sfortunatamente, il robot che avrebbe dovuto caricare i libri è andato in tilt: sta mettendo i libri sul camion in un ordine casuale! Ancora peggio, carica tutti i libri sul camion, poi controlla se sono nel giusto ordine e, in caso contrario, li scarica e ricomincia. (Questo è il temuto bogo sort.)

  • Sopran): Correggi il robot in modo che stia caricando le cose correttamente. Il giorno dopo, uno dei tuoi collaboratori ti scherza e collega il robot del caricatore ai sistemi di stampa automatizzati. Ogni volta che il robot carica un libro originale, la stampante di fabbrica esegue una duplicazione di tutte le rubriche! Fortunatamente, i sistemi di rilevamento dei bug del robot sono abbastanza sofisticati da impedire al robot di stampare ancora più copie quando incontra un libro duplicato per il caricamento, ma deve comunque caricare ogni libro originale e duplicato che è stato stampato.


2177
2018-02-21 20:14



Molte buone risposte sono già state pubblicate su questa domanda, ma credo che ci manchi davvero un'importante, ovvero la risposta illustrata.

Cosa significa dire che l'altezza di un albero binario completo è O (log n)?

Il seguente disegno descrive un albero binario. Nota come ogni livello contiene il doppio del numero di nodi rispetto al livello sopra (da qui binario):

Binary tree

La ricerca binaria è un esempio di complessità O(log n). Diciamo che i nodi nel livello inferiore dell'albero nella figura 1 rappresentano elementi in una raccolta ordinata. La ricerca binaria è un algoritmo divide et impera e il disegno mostra come occorreranno (al massimo) 4 confronti per trovare il record che stiamo cercando in questo set di dati di 16 elementi.

Supponiamo di avere invece un set di dati con 32 elementi. Continua il disegno sopra per scoprire che ora avremo bisogno di 5 confronti per trovare quello che stiamo cercando, poiché l'albero è cresciuto solo di un livello più profondo quando abbiamo moltiplicato la quantità di dati. Di conseguenza, la complessità dell'algoritmo può essere descritta come un ordine logaritmico.

Tracciare log(n) su un semplice foglio di carta, si otterrà un grafico in cui l'aumento della curva decelera come n aumenta:

O(log n)


509
2018-02-21 22:22



O(log N) fondamentalmente significa che il tempo sale linearmente mentre il n sale in modo esponenziale. Quindi se ci vuole 1 secondo per calcolare 10 elementi, ci vorrà 2 secondi per calcolare 100 elementi, 3 secondi per calcolare 1000 elementi, e così via.

Lo è O(log n) quando dividiamo e conquistiamo il tipo di algoritmi, ad esempio la ricerca binaria. Un altro esempio è l'ordinamento rapido in cui ogni volta dividiamo l'array in due parti e ogni volta che prende O(N) tempo per trovare un elemento pivot. Quindi N O(log N) 


463
2018-02-21 20:18



La spiegazione che segue sta usando il caso di un completamente equilibrato albero binario per aiutarti a capire come otteniamo la complessità del tempo logaritmico.

L'albero binario è un caso in cui un problema di dimensione n è suddiviso in sotto-problema di dimensione n / 2 fino a raggiungere un problema di dimensione 1:

height of a binary tree

Ed è così che ottieni O (log n) che è la quantità di lavoro che deve essere fatta nell'albero sopra per raggiungere una soluzione.

Un algoritmo comune con O (log n) complessità temporale è la ricerca binaria la cui relazione ricorsiva è T (n / 2) + O (1), ad ogni livello successivo dell'albero si divide il problema in metà e si fa una quantità costante di lavoro aggiuntivo.


196
2017-10-26 19:33



Se avevi una funzione che richiede:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

Quindi prende log2(n) tempo. Il Notazione Big OIn parole povere, significa che la relazione deve essere vera solo per il grande n, e che i fattori costanti e i termini più piccoli possono essere ignorati.


120
2018-02-21 20:11



Panoramica

Altri hanno fornito buoni esempi di diagrammi, come i diagrammi ad albero. Non ho visto esempi di codice semplici. Quindi oltre alla mia spiegazione, fornirò alcuni algoritmi con semplici istruzioni di stampa per illustrare la complessità delle diverse categorie di algoritmi.

Innanzitutto, ti consigliamo di avere un'idea generale del Logaritmo, da cui puoi ottenere https://en.wikipedia.org/wiki/Logarithm . Uso della scienza naturale e e il registro naturale. I discepoli di ingegneria useranno log_10 (log base 10) e gli informatici useranno log_2 (log base 2) molto, poiché i computer sono basati su binari. A volte vedrai le abbreviazioni di log naturale come ln()normalmente gli ingegneri lasciano il _10 spento e lo usano log() e log_2 è abbreviato come lg(). Tutti i tipi di logaritmi crescono in modo simile, per questo condividono la stessa categoria di log(n).

Quando guardi gli esempi di codice qui sotto, ti consiglio di guardare O (1), quindi O (n), quindi O (n ^ 2). Dopo che sei buono con quelli, allora guarda gli altri. Ho incluso esempi chiari e varianti per dimostrare come i cambiamenti sottili possano ancora comportare la stessa categorizzazione.

Puoi pensare a O (1), O (n), O (logn), ecc. Come classi o categorie di crescita. Alcune categorie avranno più tempo da fare rispetto ad altre. Queste categorie ci aiutano a ordinare le prestazioni dell'algoritmo. Alcuni sono cresciuti più velocemente man mano che l'input n cresce. La seguente tabella mostra la crescita numerica. Nella tabella seguente, si consideri log (n) come il limite massimo di log_2.

enter image description here

Esempi di codice semplice di varie categorie Big O:

O (1) - Esempi di tempo costante:

  • Algoritmo 1:

Algorithm 1 stampa ciao una volta e non dipende da n, quindi verrà sempre eseguito in tempo costante, così è O(1).

print "hello";
  • Algoritmo 2:

Algorithm 2 stampa ciao 3 volte, tuttavia non dipende da una dimensione di input. Anche se n cresce, questo algoritmo stamperà sempre solo Ciao 3 volte. Ciò detto 3, è una costante, quindi anche questo algoritmo O(1).

print "hello";
print "hello";
print "hello";

O (log (n)) - Esempi logaritmici:

  • Algoritmo 3: si comporta come "log_2"

Algorithm 3 mostra un algoritmo eseguito in log_2 (n). Si noti che l'operazione di post del ciclo for moltiplica il valore corrente di i per 2, quindi i va da 1 a 2 a 4 a 8 a 16 a 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • Algoritmo 4 - Funziona come "log_3"

Algorithm 4 dimostra log_3. Avviso i va da 1 a 3 a 9 a 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • Algoritmo 5: si comporta come "log_1.02"

L'algoritmo 5 è importante, poiché aiuta a mostrare che finché il numero è maggiore di 1 e il risultato viene moltiplicato ripetutamente su se stesso, si sta osservando un algoritmo logaritmico.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n) - Esempi di tempo lineare:

  • Algoritmo 6

Questo algoritmo è semplice, che stampa ciao n volte.

for(int i = 0; i < n; i++)
  print "hello";
  • Algoritmo 7

Questo algoritmo mostra una variazione, in cui stamperà ciao n / 2 volte. n / 2 = 1/2 * n. Ignoriamo la costante 1/2 e vediamo che questo algoritmo è O (n).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n)) - nlog (n) Esempi:

  • Algoritmo 8

Pensa a questo come una combinazione di O(log(n)) e O(n). L'annidamento dei loop for ci aiuta a ottenere il O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • Algoritmo 9

L'algoritmo 9 è come l'algoritmo 8, ma ciascuno dei loop ha permesso variazioni, che continuano a determinare il risultato finale O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2) - n al quadrato Esempi:

  • Algoritmo 10

O(n^2) si ottiene facilmente annidando lo standard per i loop.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • Algoritmo 11

Come l'algoritmo 10, ma con alcune varianti.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3) - n cubi Esempi:

  • Algoritmo 12

Questo è come l'algoritmo 10, ma con 3 cicli invece di 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • Algoritmo 13

Come l'algoritmo 12, ma con alcune varianti che producono ancora O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Sommario

Quanto sopra fornisce diversi esempi diretti e variazioni per aiutare a dimostrare quali cambiamenti sottili possono essere introdotti che davvero non cambiano l'analisi. Spero che ti dia abbastanza informazioni.


107
2018-04-26 22:50



Tempo di esecuzione logaritmico (O(log n)) significa essenzialmente che il tempo di esecuzione cresce in proporzione al logaritmo della dimensione dell'input - ad esempio, se 10 articoli richiedono al massimo un certo periodo di tempo xe 100 elementi prendono al massimo, diciamo, 2xe 10.000 oggetti al massimo 4x, quindi sembra un O(log n) complessità temporale.


84
2018-02-21 20:10



Il logaritmo

Ok proviamo e comprendiamo appieno cosa sia in realtà un logaritmo.

Immagina di avere una corda e l'abbiamo legata a un cavallo. Se la corda è direttamente legata al cavallo, la forza che il cavallo dovrà estrarre (per esempio da un uomo) è direttamente 1.

Ora immagina che la corda sia avvolta attorno a un palo. Il cavallo da scappare ora dovrà tirare molte volte di più. La quantità di volte dipende dalla ruvidità della corda e dalla dimensione del palo, ma supponiamo che moltiplicherà la forza di 10 per il tempo (quando la corda fa una virata completa).

Ora se la corda è in loop una volta, il cavallo dovrà tirare 10 volte più forte. Se l'umano decide di renderlo davvero difficile per il cavallo, può far passare di nuovo la corda intorno a un palo, aumentando la sua forza di altre 10 volte. Un terzo ciclo aumenterà nuovamente la forza di altre 10 volte.

enter image description here

Possiamo vedere che per ogni ciclo, il valore aumenta di 10. Il numero di turni necessari per ottenere qualsiasi numero è chiamato il logaritmo del numero, ovvero abbiamo bisogno di 3 post per moltiplicare la forza di 1000 volte, 6 post per moltiplicare la forza di 1.000.000.

3 è il logaritmo di 1.000 e 6 è il logaritmo di 1.000.000 (base 10).

Quindi cosa significa O (log n) in realtà? 

Nel nostro esempio sopra, il nostro 'tasso di crescita' è O (log n). Per ogni ciclo aggiuntivo, la forza che la nostra corda è in grado di gestire è 10 volte maggiore:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Ora l'esempio precedente utilizzava la base 10, ma fortunatamente la base del log è insignificante quando parliamo di notazione grande.

Ora immaginiamo che stai provando a indovinare un numero compreso tra 1 e 100.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Ora ci sono volute 7 ipotesi per farlo bene. Ma qual è la relazione qui? Qual è la maggior quantità di elementi che puoi indovinare da ogni supposizione aggiuntiva?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

Usando il grafico, possiamo vedere che se usiamo una ricerca binaria per indovinare un numero compreso tra 1 e 100, ci porterà al massimo 7 tentativi. Se avessimo 128 numeri, potremmo anche indovinare il numero in 7 tentativi ma ci saranno 129 numeri al massimo 8 tentativi (in relazione ai logaritmi, qui avremmo bisogno di 7 ipotesi per un intervallo di valori di 128, 10 ipotesi per un intervallo di valori di 1024. 7 è logaritmo di 128, 10 è il logaritmo di 1024 (base 2)).

Si noti che ho messo in grassetto "al massimo". La notazione grande si riferisce sempre al caso peggiore. Se sei fortunato, puoi indovinare il numero in un tentativo e quindi il caso migliore è O (1), ma questa è un'altra storia.

Possiamo vedere che per ogni ipotesi il nostro set di dati si sta riducendo. Una buona regola empirica per identificare se un algoritmo ha un tempo logaritmico   per vedere se il set di dati si restringe di un certo ordine dopo ogni iterazione

Che mi dici di O (n log n)?

Alla fine ti imbatterai in un momento lineraritmico O (n log (n) algoritmo. La regola generale sopra riportata si applica nuovamente, ma questa volta la funzione logaritmica deve essere eseguita n volte, ad es. riducendo la dimensione di una lista n volte, che si verifica in algoritmi come un mergesort.

Puoi facilmente identificare se il tempo dell'algoritmo è n log n. Cerca un loop esterno che itera su un elenco (O (n)). Quindi guarda se c'è un anello interno. Se il ciclo interno è taglio / riduzione il set di dati su ogni iterazione, quel loop è (O (log n), e quindi l'algoritmo complessivo è = O (n log n).

Disclaimer: L'esempio di corda-logaritmo è stato afferrato dall'eccellente Libro di Matematician's Delight di W.Sawyer. 


55
2017-10-08 14:27



Puoi pensare a O (log N) intuitivamente dicendo che il tempo è proporzionale al numero di cifre in N.

Se un'operazione esegue un lavoro a tempo costante su ogni cifra o bit di un input, l'intera operazione richiederà tempo proporzionale al numero di cifre o bit nell'input, non alla grandezza dell'ingresso; quindi, O (log N) piuttosto che O (N).

Se un'operazione esegue una serie di decisioni a tempo costante ciascuna delle quali dimezza (riduce di un fattore di 3, 4, 5 ..) la dimensione dell'input da considerare, l'intero richiederà tempo proporzionale per registrare la base 2 (base 3 , base 4, base 5 ...) della dimensione N dell'input, anziché essere O (N).

E così via.


54
2018-02-21 20:13



Il modo migliore in cui ho sempre dovuto visualizzare mentalmente un algoritmo eseguito in O (log n) è il seguente:

Se aumenti la dimensione del problema di un importo moltiplicativo (cioè moltiplichi la sua dimensione per 10), il lavoro viene aumentato solo di una quantità additiva.

Applicando questo alla tua domanda dell'albero binario in modo da avere una buona applicazione: se raddoppi il numero di nodi in un albero binario, l'altezza aumenta solo di 1 (una quantità additiva). Se lo raddoppi di nuovo, aumenta comunque di 1 (ovviamente suppongo che rimanga bilanciato e tale). In questo modo, invece di raddoppiare il tuo lavoro quando la dimensione del problema si moltiplica, stai solo facendo un po 'più di lavoro. Ecco perché gli algoritmi di O (log n) sono fantastici.


48
2018-02-22 19:51



Cosa c'è nel registroB(N)?

È il numero di volte in cui è possibile tagliare un registro di lunghezza n ripetutamente in b parti uguali prima di raggiungere una sezione di dimensione 1.


33
2018-03-19 19:28