Esistono algoritmi del mondo reale che sovraperformano notevolmente nella classe sottostante? [chiuso]

Ricerca in tabelle di dati fisse molto piccole. Una tabella hash ottimizzata può essere O (1) e tuttavia più lenta di una ricerca binaria o anche di una ricerca lineare a causa del costo del calcolo dell'hash.

Un semplice esempio è la differenza tra vari algoritmi di ordinamento. Mergesort, Heapsort e alcuni altri sono O (n log n) . Quicksort è O (n ^ 2) nel peggiore dei casi. Ma spesso Quicksort è più veloce e di fatto si comporta in media come O (n log n) . Ulteriori informazioni .

Un altro esempio è la generazione di un singolo numero di Fibonacci. L'algoritmo iterativo è O (n) , mentre l'algoritmo basato su matrice è O (log n) . Tuttavia, per il primo paio di migliaia di numeri di Fibonacci, l'algoritmo iterativo è probabilmente più veloce. Questo dipende anche dall'implementazione, naturalmente!

Algoritmi con prestazioni asintotiche migliori possono contenere operazioni costose che non sono necessarie con un algoritmo con prestazioni peggiori ma operazioni più semplici. Alla fine, la notazione O ci dice solo qualcosa sulle prestazioni quando l'argomento su cui opera aumenta drammaticamente (si avvicina all'infinito).

Moltiplicazione della matrice. L'algoritmo naïve O (n ^ 3) è spesso usato in pratica più veloce di O di Strassen (n ^ 2.8) per le matrici di piccole dimensioni; e Strassen viene usato al posto dell'algoritmo O (n ^ 2.3) Coppersmith-Winograd per matrici più grandi.

Nota: Si prega di leggere i commenti di @ back2dos di seguito e altri guru, in quanto sono in realtà più utili di quello che ho scritto - Grazie per tutti i collaboratori.

Penso che dal grafico sottostante (tratto da: Notazione Big O , cerchi "The Pessimistic Nature of Algorithms:"), puoi vedere che O (log n) non è always migliore di say, O (n). Quindi, suppongo che il tuo argomento sia valido.

Per valori pratici di n , sì. Questo risulta molto nella teoria di CS. Spesso c'è un algoritmo complicato che ha prestazioni tecnicamente migliori di Big-Oh, ma i fattori costanti sono così grandi da renderlo poco pratico.

Una volta il mio professore di geometria computazionale ha descritto un algoritmo per triangolare un poligono in tempo lineare, ma ha finito con "molto complicato, non credo che qualcuno lo abbia effettivamente implementato" (!!).

Inoltre, gli heap di Fibonacci hanno caratteristiche migliori dei normali heap, ma non sono molto popolari perché non si comportano altrettanto bene in pratica come heap normali. Questo può succedere in cascata ad altri algoritmi che usano gli heap - ad esempio, i percorsi più brevi di Dijkstra sono matematicamente più veloci con un heap di Fibonacci, ma di solito non sono in pratica.

Confronta l'inserimento in un elenco collegato e l'inserimento in un array ridimensionabile.

La quantità di dati deve essere abbastanza grande perché l'inserimento della lista collegata O (1) sia utile.

Una lista collegata ha un overhead extra per i prossimi puntatori e dereferenze. Un array ridimensionabile deve copiare i dati in giro. Quella copia è O (n), ma in pratica molto veloce.

La notazione Big-Oh viene utilizzata per descrivere il tasso di crescita di una funzione, quindi è possibile che un algoritmo O (1) sia più veloce, ma solo fino a un certo punto (il fattore costante).

Notazioni comuni:

O (1) - Il numero di iterazioni (a volte è possibile fare riferimento a questo come tempo utente trascorso dalla funzione) non dipende dalla dimensione dell'input, ed è in effetti costante.

O (n) - Il numero di iterazioni cresce in proporzione lineare alla dimensione dell'input. Significato: se l'algoritmo itera su qualsiasi input N, 2 * N volte, viene comunque considerato O (n).

O (n ^ 2) (quadratico) - Il numero di iterazioni è la dimensione di input al quadrato.

Le librerie Regex sono solitamente implementate per fare il backtracking che ha il peggior tempo esponenziale del caso invece della generazione DFA che ha una complessità di O(nm) .

Il backtrack ingenuo può essere migliore se l'input rimane sul percorso veloce o fallisce senza la necessità di tornare indietro in modo eccessivo.

(Anche se questa decisione non è solo basata sulle prestazioni, è anche per consentire riferimenti posteriori.)

Un algoritmo O(1) :

def constant_time_algorithm
  one_million = 1000 * 1000
  sleep(one_million) # seconds
end

Un algoritmo O(n) :

def linear_time_algorithm(n)
  sleep(n) # seconds
end

Chiaramente, per qualsiasi valore di n dove n < one_million , l'algoritmo O(n) fornito nell'esempio sarà più veloce dell'algoritmo O(1) .

Sebbene questo esempio sia un po 'faceto, è equivalente nello spirito al seguente esempio:

def constant_time_algorithm
  do_a_truckload_of_work_that_takes_forever_and_a_day
end

def linear_time_algorithm(n)
  i = 0
  while i < n
    i += 1
    do_a_minute_amount_of_work_that_takes_nanoseconds
  end
end

Tu devi conoscere le costanti e i coefficienti nella tua espressione O , e tu devi conoscere l'intervallo atteso di n , per determinare a priori quale algoritmo finirà per essere più veloce.

Altrimenti, devi confrontare i due algoritmi con i valori di n nell'intervallo atteso per determinare a posteriori quale algoritmo ha finito per essere più veloce.

Ordinamento:

L'ordinamento di inserimento è O (n ^ 2) ma supera gli altri algoritmi di ordinamento O (n * log (n)) per un numero ridotto di elementi.

Questo è il motivo per cui la maggior parte delle implementazioni di ordinamento utilizza una combinazione di due algoritmi. Per esempio. usa merge sort per scomporre gli array di grandi dimensioni finché non raggiungono un certo numero di array, quindi usa l'ordinamento di inserimento per ordinare le unità più piccole e unirle di nuovo con un ordinamento di tipo merge.

Vedi Timsort l'attuale implementazione predefinita degli ordinamenti Python e Java 7 che utilizzano questa tecnica.

L'algoritmo unification utilizzato nella pratica è esponenziale nel caso peggiore, per alcuni input patologici.

C'è un algoritmo di unificazione polinomiale , ma è troppo lento pratica.

Bubblesort in memoria può sovraperformare quicksort quando il programma viene scambiato su disco o deve leggere ogni elemento dal disco durante il confronto.

Questo dovrebbe essere un esempio a cui può riferirsi.

Spesso gli algoritmi più avanzati assumono una certa quantità di (costose) impostazioni. Se hai solo bisogno di eseguirlo una volta, potresti stare meglio con il metodo brute-force.

Ad esempio: ricerca binaria e ricerca tabella hash sono entrambi molto più veloci per ricerca quindi una ricerca lineare, ma richiedono di ordinare l'elenco o di costruire la tabella hash, rispettivamente.

L'ordinamento ti costerà N log (N) e la tabella hash costerà almeno N. Ora, se stai andando a fare centinaia o migliaia di ricerche, questo è ancora un risparmio ammortizzato. Ma se hai solo bisogno di fare una o due ricerche, potrebbe essere sensato solo fare la ricerca lineare e salvare i costi di avvio.

La decrittazione è spesso 0 (1). Ad esempio, lo spazio chiave per DES è 2 ^ 56, quindi la decrittografia di qualsiasi messaggio è un'operazione a tempo costante. È solo che hai un fattore di 2 ^ 56, quindi è una costante molto grande.

Mi vengono in mente diverse implementazioni di set. Uno dei più ingenui è implementarlo su un vettore, che significa remove e contains e quindi anche add tutti prendono O (N).
Un'alternativa è implementarla su un hash di uso generale, che mappa gli hash di input ai valori di input. Tale implementazione dell'insieme funziona con O (1) per add , contains e remove .

Se supponiamo che N sia circa 10 o giù di lì, la prima implementazione è probabilmente più veloce. Tutto ciò che deve fare per trovare un elemento è confrontare 10 valori con uno.
L'altra implementazione dovrà iniziare ogni sorta di trasformazioni intelligenti, che possono essere molto più costose, che fare 10 confronti. Con tutto il sovraccarico, potresti persino avere problemi di cache e quindi non importa quanto velocemente la tua soluzione sia in teoria.

Questo non significa che la peggiore implementazione che si possa pensare supererà quella decente, se N è abbastanza piccolo. Significa semplicemente per N sufficientemente piccolo, che un'implementazione ingenua, con basso ingombro e sovraccarico può effettivamente richiedere meno istruzioni e causare meno errori di cache rispetto a un'implementazione che mette al primo posto la scalabilità, e quindi sarà più veloce.

Non puoi davvero sapere quanto velocemente tutto è in uno scenario del mondo reale, finché non lo metti in uno e semplicemente lo misuri. Spesso i risultati sono sorprendenti (almeno per me).

Sì, per N opportunamente piccolo Ci sarà sempre una N, sopra la quale avrai sempre l'ordine O (1) < O (lg N) < O (N) < O (N log N) < O (N ^ c) < O (c ^ N) (dove O (1) < O (lg N) significa che in un algoritmo O (1) richiederà meno operazioni quando N è adeguatamente grande e c è una certa costante fissa che è maggiore di 1) .

Dire che un particolare algoritmo di O (1) richiede esattamente f (N) = 10 ^ 100 (un googol) e un algoritmo di O (N) richiede esattamente g (N) = 2 N + 5 operazioni. L'algoritmo O (N) offre prestazioni migliori fino a quando N è approssimativamente un googol (in realtà quando N > (10 ^ 100 - 5) / 2), quindi se ti aspetti che N sia nell'intervallo da 1000 a un miliardo potresti subire una penalità maggiore usando l'algoritmo O (1).

O per un confronto realistico, supponi di moltiplicare i numeri di n cifre. L'algoritmo Karatsuba è al massimo 3 n ^ (lg 3) operazioni (che è approssimativamente O (n ^ 1.585)) mentre l'algoritmo Schönhage-Strassen è O (N log N log log N) che è un ordine più veloce , ma per citare wikipedia:

In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2^2^15 to 2^2^17 (10,000 to 40,000 decimal digits).[4][5][6]

Quindi, se si moltiplicano i numeri di 500 cifre, non ha senso utilizzare l'algoritmo "più veloce" con grandi argomenti O.

EDIT: puoi trovare la determinazione f (N) rispetto a g (N), prendendo il limite N- > infinito di f (N) / g (N). Se il limite è 0 allora f (N) < g (N), se il limite è infinito allora f (N) > g (N), e se il limite è qualche altra costante allora f (N) ~ g (N) in termini di notazione O grande.

Il metodo simplex per programmazione lineare può essere esponenziale nel caso peggiore, mentre gli algoritmi relativamente nuovi dei punti interni possono essere polinomiali .

Tuttavia, in pratica, il caso peggiore esponenziale per il metodo simplex non emerge: il metodo simplex è veloce e affidabile, mentre i primi algoritmi per i punti interni erano troppo lenti per essere competitivi. (Ora ci sono algoritmi di punti interni più moderni che sono competitivi - ma anche il metodo simplex ...)

L'algoritmo di Ukkonen per la creazione di tentativi di suffisso è O (n log n). Ha il vantaggio di essere "on-line" - cioè, è possibile aggiungere in modo incrementale più testo.

Recentemente, altri algoritmi più complessi hanno affermato di essere più veloci nella pratica, in gran parte perché l'accesso alla loro memoria ha una localizzazione più elevata, migliorando così l'utilizzo della cache del processore ed evitando stallo della pipeline della CPU. Vedi, ad esempio, this sondaggio , che afferma che il 70-80% del tempo di elaborazione viene impiegato in attesa di memoria e questo documento che descrive l'algoritmo" wotd ".

I tentativi di suffissi sono importanti nella genetica (per la corrispondenza delle sequenze di geni) e, in modo meno importante, nell'implementazione dei dizionari di Scrabble.

C'è sempre l'algoritmo più veloce e più breve per qualsiasi problema ben definito . È puramente teoricamente l'algoritmo più veloce (asintoticamente)

Data una descrizione di un problema P e un'istanza per quel problema I , enumera tutti gli algoritmi possibili A e le prove Pr , controllando per ciascuna di tali coppie se Pr è una prova valida che A è l'algoritmo asintoticamente più veloce per P . Se trova una prova del genere, esegue A su I .

La ricerca di questa coppia a prova di problemi ha complessità O (1) (per un problema fisso P ), quindi si utilizza sempre l'algoritmo asintoticamente più veloce per il problema. Tuttavia, poiché questa costante è così indicibilmente enorme in quasi tutti i casi, questo metodo è completamente inutile nella pratica.

Molte lingue / framework usano la corrispondenza di pattern naive per far corrispondere le stringhe anziché KMP . Cerchiamo corde come Tom, New York piuttosto che ababaabababababababababababababab.