Ci sono casi in cui si preferirebbe un algoritmo di complessità del tempo maggiore di livello O su quello inferiore?

Ci sono casi in cui si preferisce la complessità temporale O(log n) alla complessità temporale O(1) ? O O(n) a O(log n) ?

Hai qualche esempio?

Ci possono essere molte ragioni per preferire un algoritmo con una maggiore complessità di tempo O su quella inferiore:

  • la maggior parte delle volte, è più difficile raggiungere una complessità Big-O più bassa e richiede un’implementazione qualificata, molta conoscenza e molti test.
  • big-O nasconde i dettagli di una costante : l’algoritmo che esegue in 10^5 è migliore dal punto di vista big-O di 1/10 1/10^5 * log(n) ( O(1) vs O(log(n) ) ma per la maggior parte ragionevole il primo funzionerà meglio, ad esempio la migliore complessità per la moltiplicazione della matrice è O(n^2.373) ma la costante è così alta che nessuna (a mia conoscenza) librerie computazionali la usa.
  • big-O ha senso quando si calcola qualcosa di grande. Se hai bisogno di ordinare un array di tre numeri, importa davvero poco se usi l’algoritmo O(n*log(n)) o O(n^2) .
  • a volte il vantaggio della complessità del tempo in minuscolo può essere davvero trascurabile. Per esempio c’è un albero di tango della struttura dati che dà una complessità temporale O(log log N) per trovare un object, ma c’è anche un albero binario che trova lo stesso in O(log n) . Anche per un numero enorme di n = 10^20 la differenza è trascurabile.
  • la complessità del tempo non è tutto. Immagina un algoritmo che gira in O(n^2) e richiede memoria O(n^2) . Potrebbe essere preferibile al tempo O(n^3) e allo spazio O(1) quando n non è molto grande. Il problema è che puoi aspettare a lungo, ma dubiti fortemente che puoi trovare una RAM abbastanza grande da poterla usare con il tuo algoritmo
  • la parallelizzazione è una buona caratteristica nel nostro mondo distribuito. Esistono algoritmi facilmente parallelizzabili e ce ne sono alcuni che non sono affatto paralleli. A volte ha senso eseguire un algoritmo su 1000 macchine di base con una complessità maggiore rispetto all’utilizzo di una macchina con una complessità leggermente migliore.
  • in alcuni punti (sicurezza) una complessità può essere un requisito. Nessuno vuole avere un algoritmo di hash in grado di hash incredibilmente veloce (perché poi altre persone possono rinforzarti più velocemente)
  • anche se questo non è correlato al cambiamento di complessità, ma alcune delle funzioni di sicurezza dovrebbero essere scritte in modo da prevenire attacchi temporali . Rimangono per lo più nella stessa class di complessità, ma sono modificati in modo che sia sempre peggio fare qualcosa. Un esempio è il confronto tra stringhe uguali. Nella maggior parte delle applicazioni ha senso rompere velocemente se i primi byte sono diversi, ma in sicurezza si aspetta ancora la fine per dire la ctriggers notizia.
  • qualcuno ha brevettato l’algoritmo di complessità inferiore ed è più economico per un’azienda utilizzare una complessità più alta rispetto al pagamento di denaro.
  • alcuni algoritmi si adattano bene a situazioni particolari. L’ordinamento di inserzione, ad esempio, ha una complessità temporale media di O(n^2) , peggiore di quicksort o mergesort, ma come algoritmo online può ordinare in modo efficiente un elenco di valori quando vengono ricevuti (come input dell’utente) dove la maggior parte altri algoritmi possono funzionare in modo efficiente solo su un elenco completo di valori.

C’è sempre la costante nascosta, che può essere inferiore nell’algoritmo O (log n ). Quindi può funzionare più velocemente nella pratica per i dati reali.

Ci sono anche problemi di spazio (es. Correre su un tostapane).

C’è anche preoccupazione per gli sviluppatori: O (log n ) può essere 1000 × più facile da implementare e verificare.

Sono sorpreso che nessuno abbia ancora menzionato le applicazioni legate alla memoria.

Potrebbe esserci un algoritmo che ha meno operazioni in virgola mobile a causa della sua complessità (cioè O (1) < O (log n )) o perché la costante di fronte alla complessità è più piccola (cioè 2 n 2 <6 n 2 ) . Indipendentemente da ciò, potreste comunque preferire l’algoritmo con più FLOP se l’algoritmo FLOP inferiore è più legato alla memoria.

Ciò che intendo per “legato alla memoria” è che si accede spesso a dati costantemente fuori cache. Per recuperare questi dati, devi estrarre la memoria dal tuo spazio di memoria reale nella cache prima di poter eseguire l’operazione su di essa. Questa fase di recupero è spesso piuttosto lenta, molto più lenta della tua stessa operazione.

Pertanto, se l’algoritmo richiede più operazioni (tuttavia queste operazioni vengono eseguite su dati che sono già nella cache [e quindi non è richiesto alcun recupero]), eseguirà ancora l’algoritmo con un numero inferiore di operazioni (che deve essere eseguito al di fuori di -cache dati [e quindi richiedono un recupero]) in termini di tempo reale di muro.

In contesti in cui la sicurezza dei dati è un problema, un algoritmo più complesso può essere preferibile a un algoritmo meno complesso se l’algoritmo più complesso ha una migliore resistenza agli attacchi temporali .

Alistra lo ha inchiodato ma non è riuscito a fornire alcun esempio, quindi lo farò.

Hai una lista di 10.000 codici UPC per ciò che il tuo negozio vende. UPC a 10 cifre, intero per prezzo (prezzo in penny) e 30 caratteri di descrizione per lo scontrino.

Approccio O (log N): hai una lista ordinata. 44 byte se ASCII, 84 se Unicode. In alternativa, considera l’UPC come int64 e ottieni 42 e 72 byte. 10.000 record: nel caso più alto si sta guardando un po ‘meno di un megabyte di spazio di archiviazione.

Approccio O (1): non memorizzare l’UPC, ma lo si utilizza come una voce nell’array. Nel caso più basso guardi quasi un terzo di un terabyte di storage.

Quale approccio usi dipende dal tuo hardware. Nella maggior parte delle configurazioni moderne ragionevoli utilizzerai l’approccio log N. Posso immaginare che il secondo approccio sia la risposta giusta se per qualche motivo sei in esecuzione in un ambiente in cui la RAM è estremamente breve ma hai un sacco di spazio di archiviazione. Un terzo di un terabyte su un disco non è un grosso problema, ottenere i tuoi dati in una sonda del disco vale qualcosa. Il semplice approccio binario richiede in media 13. (Si noti, tuttavia, che raggruppando i propri tasti è ansible ottenere questo valore in 3 letture garantite e, in pratica, si memorizzerà nella cache il primo.)

Considera un albero rosso-nero. Ha accesso, ricerca, inserimento ed eliminazione di O(log n) . Confronta con un array, che ha accesso a O(1) e il resto delle operazioni sono O(n) .

Quindi, data un’applicazione in cui inseriamo, cancelliamo o cerchiamo più spesso di quanto non accediamo e una scelta tra solo queste due strutture, preferiremmo l’albero rosso-nero. In questo caso, si potrebbe dire che preferiamo il tempo di accesso O(log n) più ingombrante dell’albero rosso-nero.

Perché? Perché l’accesso non è la nostra preoccupazione principale. Stiamo facendo un compromesso: le prestazioni della nostra applicazione sono influenzate più pesantemente da fattori diversi da questo. Consentiamo a questo particolare algoritmo di subire delle prestazioni perché facciamo grandi guadagni ottimizzando altri algoritmi.

Quindi la risposta alla tua domanda è semplicemente questa: quando il tasso di crescita dell’algoritmo non è quello che vogliamo ottimizzare , quando vogliamo ottimizzare qualcos’altro . Tutte le altre risposte sono casi speciali di questo. A volte ottimizziamo il tempo di esecuzione di altre operazioni. A volte ottimizziamo per la memoria. A volte ottimizziamo per sicurezza. A volte ottimizziamo la manutenibilità. A volte ottimizziamo i tempi di sviluppo. Anche la costante prevalente è sufficientemente bassa per la materia e si sta ottimizzando per il tempo di esecuzione quando si sa che il tasso di crescita dell’algoritmo non è il massimo impatto sul tempo di esecuzione. (Se il tuo set di dati era al di fuori di questo intervallo, ottimizzeresti il ​​tasso di crescita dell’algoritmo perché alla fine dominerebbe la costante.) Tutto ha un costo e in molti casi scambiamo il costo di un tasso di crescita più alto per algoritmo per ottimizzare qualcos’altro.

Sì.

In un caso reale, abbiamo eseguito alcuni test sulla ricerca di tabelle con chiavi di stringa sia lunghe che corte.

Abbiamo usato una std::map , una std::unordered_map con un hash che campiona al massimo 10 volte la lunghezza della stringa (i nostri tasti tendono ad essere guid-like, quindi questo è decente), e un hash che campiona ogni carattere (in teoria collisioni ridotte), un vettore non ordinato dove facciamo un == compare, e (se ricordo male) un vettore non ordinato dove memorizziamo anche un hash, prima confrontiamo l’hash, quindi confrontiamo i caratteri.

Questi algoritmi vanno da O(1) (unordered_map) a O(n) (ricerca lineare).

Per N di dimensioni modeste, molto spesso l’O (n) batte O (1). Sospettiamo che ciò sia dovuto al fatto che i contenitori basati su nodes richiedevano che il nostro computer passasse di più nella memoria, mentre i contenitori lineari non lo facevano.

O(lg n) esiste tra i due. Non ricordo come è stato.

La differenza di prestazioni non era così grande, e su set di dati più grandi, quello basato su hash funzionava molto meglio. Quindi abbiamo bloccato la mappa non ordinata basata sull’hash.

In pratica, per dimensioni ragionevoli n, O(lg n) è O(1) . Se il tuo computer ha solo spazio per 4 miliardi di voci nella tua tabella, allora O(lg n) è limitato sopra di 32 . (lg (2 ^ 32) = 32) (in informatica, lg è una mano breve per log based 2).

In pratica, gli algoritmi lg (n) sono più lenti degli algoritmi O (1) non a causa del fattore di crescita logaritmico, ma perché la porzione lg (n) di solito significa che c’è un certo livello di complessità nell’algoritmo, e che la complessità aggiunge un fattore costante maggiore di qualsiasi “crescita” dal termine lg (n).

Tuttavia, algoritmi O (1) complessi (come la mapping hash) possono facilmente avere un fattore costante simile o maggiore.

La possibilità di eseguire un algoritmo in parallelo.

Non so se c’è un esempio per le classi O(log n) e O(1) , ma per alcuni problemi, si sceglie un algoritmo con una class di complessità più alta quando l’algoritmo è più facile da eseguire in parallelo.

Alcuni algoritmi non possono essere parallelizzati ma hanno una class di complessità così bassa. Considera un altro algoritmo che raggiunge lo stesso risultato e può essere facilmente parallelizzato, ma ha una class di complessità più alta. Se eseguito su una macchina, il secondo algoritmo è più lento, ma quando viene eseguito su più macchine, il tempo di esecuzione reale diventa sempre più basso mentre il primo algoritmo non può accelerare.

Supponiamo che tu stia implementando una lista nera su un sistema incorporato, in cui i numeri tra 0 e 1.000.000 potrebbero essere inseriti nella lista nera. Questo ti lascia due opzioni possibili:

  1. Utilizzare un set di bit di 1.000.000 bit
  2. Utilizzare una matrice ordinata degli interi inseriti nella lista nera e utilizzare una ricerca binaria per accedervi

L’accesso al bitset garantirà un accesso costante. In termini di complessità temporale, è ottimale. Sia da un punto di vista teorico che da un punto di vista pratico (è O (1) con un overhead costante estremamente basso).

Tuttavia, potresti preferire la seconda soluzione. Soprattutto se si prevede che il numero di numeri inseriti in blacklist sia molto piccolo, in quanto sarà più efficiente in termini di memoria.

E anche se non si sviluppa per un sistema embedded in cui la memoria è scarsa, posso solo aumentare il limite arbitrario da 1.000.000 a 1.000.000.000.000 e fare lo stesso argomento. Quindi il bitset richiederebbe circa 125G di memoria. Avere una complicanza di O (1) nel peggiore dei casi potrebbe non convincere il tuo capo a fornirti un server così potente.

Qui, preferirei fortemente una ricerca binaria (O (log n)) o un albero binario (O (log n)) sul set di bit O (1). E probabilmente, una tabella di hash con la sua complessità nel caso peggiore di O (n) batterà tutti nella pratica.

La mia risposta qui Selezione rapida ponderata casuale su tutte le righe di una matrice stocastica è un esempio in cui un algoritmo con complessità O (m) è più veloce di uno con complessità O (log (m)), quando m non è troppo grande.

Le persone hanno già risposto alla tua domanda esatta, quindi affronterò una domanda leggermente diversa a cui le persone potrebbero effettivamente pensare quando vengono qui.

Un sacco di algoritmi e strutture dati “O (1)” in realtà richiedono solo O (1) tempo previsto, il che significa che il loro tempo medio di esecuzione è O (1), probabilmente solo in base a determinati presupposti.

Esempi comuni: hashtables, espansione di “liste di array” (ovvero matrici / vettori di dimensioni dinamiche).

In tali scenari, potresti preferire utilizzare strutture dati o algoritmi il cui tempo è garantito per essere assolutamente limitato logaritmicamente, anche se in media possono avere un rendimento peggiore.
Un esempio potrebbe quindi essere un albero di ricerca binario bilanciato, il cui tempo di esecuzione è peggiore in media ma migliore nel peggiore dei casi.

Una domanda più generale è se ci sono situazioni in cui si preferirebbe un algoritmo O(f(n)) ad un algoritmo O(g(n)) anche se g(n) << f(n) come n tende all'infinito. Come altri hanno già menzionato, la risposta è chiaramente "sì" nel caso in cui f(n) = log(n) e g(n) = 1 . A volte sì anche nel caso in cui f(n) è polinomiale ma g(n) è esponenziale. Un esempio famoso e importante è quello dell'algoritmo Simplex per risolvere problemi di programmazione lineare. Negli anni '70 è stato dimostrato che era O(2^n) . Quindi, il suo comportamento nel caso peggiore è irrealizzabile. Ma - il suo comportamento nel caso medio è estremamente buono, anche per problemi pratici con decine di migliaia di variabili e vincoli. Negli anni '80 sono stati scoperti algoritmi di tempo polinomiale (come l'algoritmo di un punto interno di Karmarkar ) per la programmazione lineare, ma 30 anni dopo l'algoritmo di simplex sembra ancora essere l'algoritmo di scelta (eccetto per alcuni problemi molto grandi). Ciò è ovvio per il fatto che il comportamento dei casi medi è spesso più importante del comportamento del caso peggiore, ma anche per una ragione più sottile che l'algoritmo del simplesso è in un certo senso più informativo (ad esempio, le informazioni sulla sensibilità sono più facili da estrarre).

Per mettere i miei 2 centesimi in:

A volte un algoritmo di complessità peggiore viene selezionato al posto di uno migliore, quando l’algoritmo gira su un determinato ambiente hardware. Supponiamo che il nostro algoritmo O (1) acceda in modo non sequenziale ad ogni elemento di una matrice di dimensioni molto grandi, per risolvere il nostro problema. Quindi metti quella matrice su un disco rigido meccanico o su un nastro magnetico.

In tal caso, l’algoritmo O (logn) (supponiamo che acceda al disco in modo sequenziale), diventa più favorevole.

C’è un buon caso d’uso per usare un algoritmo O (log (n)) invece di un algoritmo O (1) che le numerose altre risposte hanno ignorato: immutabilità. Le mappe hash hanno O (1) put e gets, presupponendo una buona distribuzione dei valori hash, ma richiedono uno stato mutabile. Le mappe ad albero immutabili hanno O (log (n)) put e gets, che è asintoticamente più lento. Tuttavia, l’immutabilità può essere abbastanza valida da compensare le prestazioni peggiori e nel caso in cui siano necessarie più versioni della mappa, l’immutabilità consente di evitare di dover copiare la mappa, che è O (n), e quindi può migliorare prestazione.

Semplicemente: perché il coefficiente – i costi associati all’impostazione, all’archiviazione e al tempo di esecuzione di quel passo – può essere molto, molto più grande con un problema di big-O più piccolo rispetto a uno più grande. Big-O è solo una misura della scalabilità degli algoritmi.

Considera l’esempio seguente del dizionario dell’hacker, che propone un algoritmo di ordinamento basato sull’interpretazione a più mondi della meccanica quantistica :

  1. Permuta l’array in modo casuale usando un processo quantistico,
  2. Se l’array non è ordinato, distruggi l’universo.
  3. Tutti gli universi rimanenti sono ora ordinati [incluso quello in cui ti trovi].

(Fonte: http://catb.org/~esr/jargon/html/B/bogo-sort.html )

Si noti che il big-O di questo algoritmo è O(n) , che batte qualsiasi algoritmo di ordinamento noto fino ad oggi su articoli generici. Anche il coefficiente del passo lineare è molto basso (dal momento che è solo un confronto, non uno scambio, che viene fatto in modo lineare). Un algoritmo simile potrebbe, infatti, essere utilizzato per risolvere qualsiasi problema sia in NP che in co-NP in tempo polinomiale, dal momento che ogni ansible soluzione (o ansible prova che non c’è soluzione) può essere generata usando il processo quantistico, quindi verificata in tempo polinomiale.

Tuttavia, nella maggior parte dei casi, probabilmente non vogliamo correre il rischio che i mondi multipli non siano corretti, per non parlare del fatto che l’atto di implementare la fase 2 è ancora “lasciato come esercizio per il lettore”.

In qualsiasi momento in cui n è limitato e il moltiplicatore costante dell’algoritmo O (1) è superiore al limite su log (n). Ad esempio, la memorizzazione dei valori in un hashset è O (1), ma potrebbe richiedere un calcolo costoso di una funzione hash. Se gli elementi di dati possono essere paragonati banalmente (rispetto ad un certo ordine) e il legame su n è tale che log n è significativamente inferiore al calcolo hash su un singolo elemento, quindi l’archiviazione in un albero binario bilanciato può essere più veloce dell’archiviazione in un hashset.

In una situazione in tempo reale in cui è necessario un limite superiore fisso, selezionare ad esempio un heapsort anziché un Quicksort, poiché il comportamento medio di heapsort è anche il suo comportamento peggiore.

Aggiungendo alle già buone risposte. Un esempio pratico potrebbe essere gli indici Hash e gli indici B-tree nel database postgres.

Gli indici hash formano un indice di tabella hash per accedere ai dati sul disco mentre btree come suggerisce il nome usa una struttura dati Btree.

Nel tempo di Big-O questi sono O (1) contro O (logN).

Gli indici di hash sono attualmente scoraggiati nei postgres poiché in una situazione di vita reale, in particolare nei sistemi di database, raggiungere l’hashing senza collisione è molto difficile (può portare a una complessità peggiore di O (N)) e per questo è ancora più difficile da fare li crash sicuro (chiamato write ahead logging – WAL in postgres).

Questo compromesso è fatto in questa situazione dal momento che O (logN) è abbastanza buono per gli indici e l’implementazione di O (1) è piuttosto difficile e la differenza di orario non sarebbe importante.

Quando n è piccolo e O(1) è costantemente lento.

  1. Quando l’unità di lavoro “1” in O (1) è molto alta rispetto all’unità di lavoro in O (log n) e la dimensione impostata prevista è di piccole dimensioni. Ad esempio, è probabilmente più lento calcolare i codici hash del dizionario piuttosto che iterare un array se ci sono solo due o tre elementi.

o

  1. Quando la memoria o altri requisiti di risorse non temporali nell’algoritmo O (1) sono eccezionalmente grandi rispetto all’algoritmo O (log n).
  1. quando si riprogetta un programma, si scopre che una procedura è ottimizzata con O (1) invece di O (lgN), ma se non è il collo di bottiglia di questo programma, ed è difficile capire l’algoritmo O (1). Quindi non dovresti usare l’algoritmo O (1)
  2. quando O (1) richiede molta memoria che non puoi fornire, mentre il tempo di O (lgN) può essere accettato.

Questo è spesso il caso per le applicazioni di sicurezza che vogliamo progettare problemi i cui algoritmi sono lenti di proposito per impedire a qualcuno di ottenere una risposta a un problema troppo rapidamente.

Ecco un paio di esempi in cima alla mia testa.

  • L’hashing della password viene talvolta reso arbitrariamente lento al fine di rendere più difficile l’individuazione delle password tramite la forza bruta. Questo post sulla sicurezza delle informazioni ha un punto elenco (e molto altro).
  • Bit Coin usa un problema controllabilmente lento per una rete di computer da risolvere al fine di “estrarre” le monete. Ciò consente alla valuta di essere estratta ad un tasso controllato dal sistema collettivo.
  • I cifrari asimmetrici (come RSA ) sono progettati per rendere la decrittazione senza che le chiavi siano intenzionalmente lente per impedire a qualcun altro senza la chiave privata di decifrare la crittografia. Gli algoritmi sono progettati per essere spezzati nel tempo auspicato O(2^n) dove n è la lunghezza del bit della chiave (questa è forza bruta).

Altrove in CS, Quick Sort è O(n^2) nel caso peggiore ma nel caso generale è O(n*log(n)) . Per questo motivo, l’analisi “Big O” a volte non è l’unica cosa che ti interessa quando analizzi l’efficienza dell’algoritmo.