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