Conosco gli algoritmi fondamentali e le sue complessità. per esempio se la ricerca binaria ha complessità O (log n), allora come posso dimostrarlo matematicamente?
Suppongo che tu stia chiedendo come misurare la complessità temporale dell'algoritmo per quanto riguarda il suo input (in che modo il tempo dell'algoritmo cresce man mano che N cresce). Un modo è quello di modellare l'algoritmo sotto forma di un'equazione di ricorrenza e quindi risolvere tramite una serie di tecniche. Le tecniche comuni sono teorema principale, sostituzione, alberi di ricorrenza, ...
L'algoritmo di ricerca binaria può essere visto come recidive della divisione di N a metà con un confronto. Quindi T (n) = T (n / 2) + 1. Risolvi questo dal teorema principale per mostrare che la funzione è log n.
Per una panoramica completa di questo tipo di cose ti suggerisco di lavorare su queste due classi:
Big Oh non è in realtà una descrizione della complessità dell'algoritmo, come nel modo in cui vengono prese molte decisioni e diramazioni, Big Oh è una descrizione o misura delle risorse di calcolo utilizzate da un algoritmo.
In ogni caso dovrai familiarizzare con la matematica complessa dietro la teoria della complessità, conoscere le classi di complessità P, NP, EXPTIME e tutte quelle cose divertenti.
Informalmente, dovresti usare un argomento come: let f (n) il numero di operazioni necessarie per eseguire una ricerca binaria su n elementi. Quindi, prima di tutto, sostieni che la relazione
f(n) = 2 f(n/2) + c
contiene e quindi usa il Teorema master.
Formalmente la "dimostrazione" della complessità è qualcosa che mi ha sempre infastidito, dal momento che quest'area teorica sembra (almeno come presentata nell'informatica introduttiva) cercare di applicare la matematica formale a una base vaga e informale. (Ad esempio, cosa conta esattamente come "operazione"?)
Per un'introduzione alle strutture dati e agli algoritmi, Cormen & al Introduzione agli algoritmi è davvero eccezionale.
Per quanto riguarda il caso specifico delle complessità di calcolo, in genere si tratta di esprimerlo come una relazione ricorsiva, quindi dimostrare che la relazione è vera, quindi ridurre questa relazione ricorsiva a una formula più gestibile.
Il Teorema di Master è utile nell'ultima fase, leggi l'articolo di wikipedia, dovrebbe essere sufficiente per il tuo semplice esempio .
Solo per ricerca binaria!
Ecco il mio modo di farlo:
Per implementare la ricerca binaria su un elenco ordinato che contiene N elementi, continuiamo a dividere l'elenco a metà fino a quando non "angoliamo" la chiave. Questo ci dice che la dimensione del problema diminuisce della metà, [Eg. 100: 50: 25: 12: 6: 3: 1], fino a raggiungere (caso peggiore) 1 !
Questo ci dà una progressione geometrica con un rapporto comune = 1/2 e il nesimo termine è 1.
La formula GP è:
A n = A 1 r n-1 che porta a
1 = A 1 (1/2) n-1
Diventa più facile dopo questo: dividi entrambi i lati di A 1 , Moltiplica per Log 2 e risolvi per N!
Dovresti darti il numero di passaggi per raggiungere A n che è Log 2 A1 + 1 che a sua volta è O (log n )
Ci sono tecniche matematiche per dimostrare grande-oh. IIRC là dove sono coinvolte alcune equazioni alle differenze. Qualsiasi libro di testo decente sull'argomento dovrebbe essere in grado di insegnarti le corde.
Leggi altre domande sui tag c++ algorithms math