Note de curs, clasele 9-10, 5 octombrie 2012
From Algopedia
Jump to navigationJump to search
Complexități
- Notația O(), creșterea asimptotică a funcțiilor
- Cazul cel mai rău / cel mai bun / mediu
- Exemplu: bubble sort
- Complexitate amortizată
- Exemplu: căutarea într-un vector nesortat / sortat
Heaps
- Ce operații dorim: inserare, extragere de minim
- Implementări naive: vector, vector ordonat, listă.
- Calcul de complexitate pentru fiecare
- Structură arborescentă
- Implementare pe un vector
- Analiza complexității, în special pentru heapify()
- Aplicații: heapsort, priority queue
Temă
- Să se interclaseze k vectori sortați a câte n elemente fiecare