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