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)