Quali sono gli algoritmi che voi persone trovate di avere un'analisi della complessità sorprendente (dura, strana) in termini di entrambi - Notazione O risultante e unicità nel modo in cui vengono analizzati?Algoritmi per Big O Analysis
La complessità non deterministica del polinomio ottiene il mio voto, specialmente con la possibilità (improbabilmente considerata improbabile) che possa rivelarsi uguale al polinomio. Allo stesso modo, tutto ciò che può teoricamente beneficiare del calcolo quantistico (N.B. questo insieme non è affatto tutti gli algoritmi).
L'altro che otterrebbe il mio voto sarebbe operazioni matematiche comuni su numeri arbitrari di precisione: è qui che devi considerare che moltiplicare i numeri grandi è più costoso che moltiplicare quelli piccoli. C'è una grande quantità di analisi su Knuth (che non dovrebbe essere una novità per nessuno). Il metodo di Karatsuba è abbastanza accurato: taglia i due fattori a metà per cifra (A1; A2) (B1; B2) e moltiplica A1 B1, A1 B2, A2 B1, A2 B2 separatamente e poi combina i risultati. Recurse se desiderato ...
Il metodo di Karatsuba è elegante, questo è vero. Tuttavia, poiché una trasformata di Fourier veloce esegue una convoluzione, può essere utilizzata per eseguire le moltiplicazioni più veloci conosciute, supponendo che i numeri siano abbastanza grandi da giustificare l'aggravamento della scrittura di un FFT di input misto e la sua sintonizzazione. –
Hmm, dovrò cercarlo. Quanto sono precisi i componenti per garantire la moltiplicazione esatta di interi? – Edmund
Come ho capito, hai semplicemente bisogno di precisione sufficiente per contenere il numero finale. Sebbene la tecnica di moltiplicazione FFT possa essere utilizzata direttamente anche sui tipi interi, è sempre possibile fornire risposte precise. Non ho la mia copia di Knuth qui, ma penso che menziona la tecnica e ci passa sopra. –
Questo è un po 'semplice ma Comb Sort mi soffia un po' la mente.
http://en.wikipedia.org/wiki/Comb_sort
Si tratta di un semplice algoritmo come per la maggior parte si legge come un troppo complicato bubble sort, ma è O (n * log [n]). Trovo che sia leggermente impressionante.
Anche la pletora di algoritmi per le trasformate di Fourier veloci è impressionante, la matematica che dimostra la loro validità è entusiasmante ed è stato divertente provare a provarne alcuni da solo.
http://en.wikipedia.org/wiki/Fast_Fourier_transform
posso abbastanza facilmente capire la radice primaria, più radix primo, e gli algoritmi radix contrastanti, ma uno che lavora sui set le cui dimensioni sono primi è piuttosto fresco.
ho (abbastanza) alcuni esempi:
L'analisi di ricerca ordinata in 2D è piuttosto interessante. Hai una matrice numerica bidimensionale di numeri NxN in cui ogni riga è ordinata da sinistra a destra e ogni colonna è ordinata dall'alto in basso. L'attività è trovare un numero particolare nell'array.
L'algoritmo ricorsivo: selezionare l'elemento nel mezzo, confrontare con il numero di destinazione, scartare un quarto dell'array (a seconda del risultato del confronto), applicare ricorsivamente ai restanti 3 trimestri è piuttosto interessante da analizzare.
Tipo di shell. Ci sono un sacco di varianti con vari incrementi, la maggior parte dei quali non ha alcun beneficio se non quello di fare il complexity analysis simpler.
È un algoritmo? – shoosh
@ p Probabilmente questa risposta va bene, anche se è solo link. "La funzione di Ackermann" è sufficiente per trovarla su Internet e la domanda - che è probabilmente fuori tema - richiede solo algoritmi, non spiegazioni. – royhowie