Dynamické pole

Ako funguje dynamické pole?

  • V jazyku Java je implementované v ArrayList-e, podľa dokumentácie majú operácie nasledovnú zložitosť:

  • V jazyku C++ je implementované vo vector-e, zložitosť podľa dokumentácie:
  • V jazyku Python je implementové v zozname list, [].

  • Podľa wikipédie sa pole v jednotlivých implementáciach zväčšuje rôzne: faktor zväčšenia

Napr. ak začíname s kapacitou 100 prvkov, tak postupné pridávanie prvkov má zložitosť:

$$1+1+..+1+(200+101)+1+1+...+1+(400+201)+1+1+...$$

Zložitosť jednej operácie pridania je teda $O(n)$. Pridanie $n$ prvkov má teda zložitosť $O(n^2)$.

Toto je len hrubý horný odhad, tesný odhad pre pridanie $n$ prvkov je $\Theta(n)$. Pridanie každého prvku má zložitosť $O(1)$ a v prípade naplnenia kapacity ešte navyše nová veľkosť poľa, teda v uvedenom príklade $200+400+800+1600+... = O(n)$.

Bola definovaná amortizovaná zložitošť, určujúca "priemernú časovú zložitosť". Na výpočet zložitosti celého programu teda môžeme počítať počet operácií $\times$ amortizovaná zložitosť.

Amortizovaná zložitosť

  • zásobník s MULTIPOP výberom

      PUSH - vložiť jeden prvok na vrch
      POP - vybrať jeden prvok
      MULTIPOP - vybrať $k$ prvkov
  • binárne počítadlo ($k$-bitové)

      pole $k$ bitov (0, 1)
    
      INCR - zvýšiť počítadlo o jedna
    
    

    napr.:

      0000
      0001
      0010
      0011
      0100
      0101 ... 1+4 = 5
      0110
      0111
      1000
    
    

    zoskupíme po bitoch/stĺpcoch:

      - posledný bit sa mení stále ... O(n)
      - predposledný bit sa mení po každom druhom pripočítaní ... O(n/2)
      - tretí bit sprava sa mení po 4 pripočítaniach ... O(n/4)
    
    

    $$n+\frac{n}{2}+\frac{n}{4}+...= 2n $$

    Celková zložitosť $n$ operácií je $O(2n)$, a teda amortizovaná zložitosť je $O(\frac{2n}{n}) = O(2) = O(1) $, t.j. konštantná.

  • dynamické pole

In [ ]: