Note de curs, clasele 11-12, 5 octombrie 2012: Difference between revisions

From Algopedia
Jump to navigationJump to search
 
(No difference)

Latest revision as of 14:57, 25 January 2013

Structuri de mulțimi disjuncte

  • Ce operații dorim: test de apartenență / uniunea a două mulțimi
  • Implementare naivă: vectori (v[x] == v[y] dacă x și y sunt în aceeași mulțime). Analiza complexității
  • Implementare arborescentă
    • Optimizări: echilibrare și compresia căii
  • Analiză de complexitate (fușerită, că mă depășește)
  • Exemple: determinarea componentelor conexe, Kruskal, LCA offline
  • Discuție tangentă: comparația algoritmilor lui Prim și Kruskal

LCA online și RMQ

  • Parcurgeri Euler
    • Reducerea LCA online la RMQ
  • RMQ: varianta naivă, O(), O(), O(1) per query