Izpitno vprašanje RAČ2PRA 3600

Iz MaFiRaWiki

Vsebina

Vprašanje

Kaj pomeni časovna in kaj prostorska zahtevnost algoritma? Kaj nam ta informacija sploh pove?

Odgovor

Časovna zahtevnost

Koliko časa dani algoritem zahteva za izvajanje. Pri časovni zahtevnosti nas zanima rast časa v odvisnosti od velikosti problema.


Kaj nam časovna zahtevnost sploh pove:

  • Poenostavljeno:
    • Imamo algoritem, za katerega vemo, da je njegova časovna zahtevnost O(n).
    • Imamo problem velikosti 100.
    • Koliko časa se bo izvajal na računalniku?
    o ne vemo
    o denimo, da je to trajalo 5 sekund
    • Vzemimo problem velikosti 300.
    • Koliko časa se bo ta izvajal?
    o rast časa za ta algoritem je linearna
    o 3 krat večji problem, 3 krat dlje traja, 15 sekund (približno)
  • Dejanska časovna zahtevnost:
    • Imamo algoritem, za katerega vemo, da je njegova časovna zahtevnost O(n).
    • Imamo problem velikosti 100.
    • Čas izvajanja: T1(n) = n - 95.
    • T1(100) = 100 - 95 = 5 sekund
    • Imamo problem velikosti 300.
    • T1(300) = 300 - 95 = 205 sekund

Analiza:

  • določimo najhitreje rastoči faktor
  • zanemarimo počasneje rastoče faktorje
  • zanemarimo konstantni faktor pri najhitreje rastočem členu
  • dobimo formulo za časovno zahtevnost algoritma.


Potrebnemu času za izvajanje algoritma pri najneugodnejših in najugodnejših podatkih pravimo časovna zahtevnost v najslabšem in najboljšem primeru. Na poenostavljen način lahko dobimo povprečno oz. pričakovano časovno zahtevnost kot vsoto njenih možnih vrednosti pomnoženih z njihovimi verjetnostmi.

Prostorska zahtevnost

Pod tem pojmom razumemo količino prostora, ki ga potrebujemo za rešitev problema: odvisnost prostora od števila podatkov.

Dejansko prostorsko zahtevnost algoritma ugotavljamo empirično ali analitično. Najpogosteje le ocenjujemo potreben prostor izvajanja algoritma (če poznamo algoritem in zmogljivost računalnika). Velikokrat je prostorska zahtevnost konstantna: P(n)=O(1), kar pomeni, da ne glede na število podatkov potrebujemo enako mnogo prostora.


V splošnem je tako časovna kot prostorska zahtevnost algoritma odvisna od podatkov za dani algoritem (tipično od "velikosti" vhodnih podatkov).

Osebna orodja