Note de curs, clasele 11-12, 18 ianuarie 2013
From Algopedia
Jump to navigationJump to search
Noțiuni de probabilități
- experiment Bernoulli; experiment binomial B(n, p)
- valoarea așteptată pt. Bernoulli: p; pentru binomial: np
- nr. de experimente până la succes: distribuție geometrică
- valoarea așteptată a nr. de experimente: 1 / p
Skip lists
- operații dorite: inserare / ștergere / căutări / minim / maxim / cea mai apropiată valoare
- comparația cu arbori: oferă complexitate logaritmică, implementare greoaie
- comparația cu hash tables: nu suportă ordonare
- punct de pornire: listă înlănțuită
- adăugăm nivelul 2 cu pointeri din 2 în 2 -- căutarea cere acum n / 2 + 1 comparații
- nivelul 3 cu pointeri din 4 în 4 -- căutarea cere acum n / 4 + 3 comparații
- generalizare probabilistică
- santinelă cu NIL = valoare infinită la sfârșit
- limitarea nivelului la max level
- pseudocod pentru căutare
- pseudocod pentru inserare, ștergere
- pseudocod pentru alegerea aleatoare a nivelului (distribuție geometrică, nu uniformă)
- atenție la factorii constanți la probleme subliniare
- constanta 2 înseamnă că pot procesa doar O(n) valori în loc de O(n2)
1-2 skip lists
- deterministe, dar mai complicate / mai scumpe
- între oricare 2 noduri de înălțime h există 1 sau 2 noduri de înălțime h - 1.
- inserare: creșterea elementului din mijloc dacă au apărut 3 la același nivel (presupune realocare, deci poate fi O(log2 n).
- la fel și la ștergere
- soluție 1: listă de pointeri în loc de vector de pointeri - triplează necesarul de memorie
- discuție tangentă despre alocarea dinamică
- e scumpă, alocarea oriunde în memorie duce de râpă cache-ul de procesor
- soluție 2: pointerii next pentru fiecare element sunt într-un vector de pointeri realocat dinamic (dublare / înjumătățire când este cazul)