Časovna in prostorska zahtevnost

Časovna in prostorska zahtevnost

Avtor: Matija Lokar

Več o projektu...

Še malo o časovni zahtevnosti

  • Dan je nek problem.
  • Na voljo imamo računalnik in dva algoritma za reševanje tega problema. Prvi je , drugi pa .

  • Rešujemo problem velikosti 1000. Kateri algoritem bo hitrejši: tisti z linearno časovno zahtevnostjo ali tisti s kvadratično?

    • Ne vemo!
    • Morda prvi, morda drugi, morda bosta enako hitra, ...
    • Vemo pa – ko bomo vzeli problem velikosti 5000, lahko pričakujemo, da se bo pri linearnem algoritmu čas povečal približno , pri kvadratičnem pa .

Kaj nam pove časovna zahtevnost?

  • Imamo algoritem, za katerega vemo, da je njegova časovna zahtevnost .
  • Imamo problem velikosti 100.

  • Koliko časa se bo izvajal na računalniku?

    • Ne vemo!
    • Denimo, da je to trajalo 5 sekund.
  • Vzemimo problem velikosti 300

  • Koliko časa se bo ta izvajal?

    • Pravzaprav ne vemo, lahko pa pričakujemo naslednje

      • Ker je rast časa za ta algoritem linearna
      • večji problem - dlje, torej cca 15 sekund

  • Kaj pa problem velikosti 900?

    • Spet pravzaprav ne vemo, lahko pa pričakujemo

      • Ker je rast časa za ta algoritem linearna
      • večji problem - dlje, torej cca 45 sekund

Kaj nam torej pove časovna zahtevnost?

  • Imamo algoritem, za katerega vemo, da je njegova časovna zahtevnost .
  • Imamo problem velikosti 100.

  • Koliko časa se bo izvajal na računalniku?

    • Ne vemo!
    • Denimo, da je to trajalo 5 sekund.
  • Vzemimo problem velikosti 300

  • Koliko časa se bo ta izvajal?

    • Ker je rast časa za ta algoritem kvadratična

    • Ne vemo, a pričakujemo lahko:

      • večji problem - () dlje, torej cca 45 sekund

  • Kaj pa problem velikosti 1000?

    • Ker je rast časa za ta algoritem kvadratična
    • večji problem – pričakujemo lahko, da se bo izvajal dlje, torej cca 500 sekund

Kaj nam pove časovna zahtevnost?

  • Seveda smo pri obeh primerih HUDOOOO poenostavili
  • Dva algoritma

  • Dejanska čas. zahtevnost naj bo

  • Oba
  • ,
  • ,
  • ,
  • ,
  • ,
  • ,
  • ,
  • Če podvajamo velikost problema, se rast časa "umiri" pri podvojenem času
  • Pri časovni zahtevnosti nas zanima asimptotična RAST časa v odvisnosti od velikosti problema

Kaj moramo zagotovo vedeti o časovni zahtevnosti

  • Pri časovni zahtevnosti se ne ukvarjamo s časom, ki bo potreben za izvedbo konkretnega problema na konkretnem računalniku

    • Ker nam pravzaprav to ne pove nič (različni problemi, različni računalniki, ...)
  • Zanima nas, kaj se zgodi, če rešujemo z istim algoritmom problem, ki je , , večji (ima toliko več podatkov)

  • Če je algoritem linearen (), pričakujemo da bo čas izvajanja na istem računalniku , , daljši.

    • Če je torej računalnik dal rezultate za problem velikosti 1000 po 7sek, bomo na rezultate problema velikosti 2000 čakali 14sek, za velikost 10000 70sek, za velikost 100000 700sek, ...

  • Če je algoritem kvadratičen (), pričakujemo da bo čas izvajanja na istem računalniku , , daljši.

    • Če je torej računalnik dal rezultate za problem velikosti 1000 po 3sek, bomo na rezultate problema velikosti 2000 čakali 12sek, za velikost 10000 300sek, za velikost 100000 30000sek, ...
  • Če je algoritem ekponentne narave (), pričakujemo da bo čas izvajanja na istem računalniku , , daljši.

Kaj "povemo", če rečemo, da je nek algoritem kvadratične časovne zahtevnosti

  • Praviloma za noben algoritem ne izpeljemo točne formule za časovno zahtevnost
  • Običajno zahtevnost kar ocenimo z notacijo
  • V se skrivajo najrazličnejše funkcije – /10000 – 100n -50, 1000 ... – vse take, kjer od nekega naprej na vrednost bistveno vpliva le še .
  • Zato z notacijo pravzaprav govorimo le o rasti časa (v odvisnosti od velikosti problema) – torej o tem, kaj se bo dogajalo s časom, če bomo vzeli , , večji problem in ga reševali na istem računalniku.

Kaj je torej s časom

  • Če je nek algoritem linearne časovne zahtevnosti torej vemo, da bo (ko so problemi dovolj veliki) čas, potreben za izvajanje na istem računalniku, rastel linearno sorazmerno v odvisnosti od velikosti ( večji problem, več časa)
  • Nikakor pa to ne pomeni, da se bo npr. problem velikosti 100 pri linearnem algoritmu izvajal 100 sekund (ali pa potreboval čas osnovne operacije)
  • Lahko pa pričakujemo, da če vemo, da je algoritem linearne časovne zahtevnosti in bomo vzeli večji problem, da se bo ta verjetno reševal dlje časa.
  • Zakaj verjetno: to je seveda res le, če so problemi že dovolj veliki, da je "prevladal" linearni člen (da linearni člen v točni formuli za čas prinese največ k "vrednosti" te formule)

Kaj povedati o časovni zahtevnosti algoritma

  • Najprej moramo opredeliti, kaj je velikost problema

    • Poišči kateri znak v tabeli nizov nastopa največkrat

      • Velikost problema je: skupna dolžina vseh nizov

    • Dana je tabela nizov, ki so vsi dolžine 100. Poišči kateri znak v tabeli nastopa največkrat

      • Velikost problema je: velikost tabele

  • Nato moramo določiti ustrezno formulo, s katero povemo, kako je število osnovnih operacij odvisno od velikosti problema

    • .....
    • : velikost problema
    • Točne formule (funkcije) se običajno ne da napisati (prezapletena, povezana z verjetnostjo ...)
    • Zato naredimo oceno in vse izrazimo kar z notacijo.
  • Zavedati se je potrebno, da gre za oceno in da je zaradi notacije govora o rasti časa in ne o točnem času.

Tri zahtevnosti

  • Običajno so algoritmi taki, da se čas izvajanja lahko zelo razlikuje, če so podatki

    • "idealni"
    • "običajni"
    • "zlobni"

  • Npr. bisekcija

    • Če iščemo ravno srednji podatek – idealni podatki – algoritem se takoj zaključi
    • Če iščemo podatek, ki ga ni – "zlobni" podatki – največ dela

  • Zato: časovna zahtevnost v najboljšem primeru, najslabšem primeru in pričakovana časovna zahtevnost

    • Minimalna
    • Pričakovana
    • Maksimalna
  • Najboljši primer ni, da vzamemo velikost problema 1, ...
  • Še vedno: zahtevnost v odvisnosti od velikosti problema, le vzamemo "idealne" ("zlobne", "običajne") podatke

Prostorska zahtevnost

  • Celotna zgodba velja tudi za prostorsko zahtevnost
  • Zanima nas količina dodatnega prostora (spremenljivk ...)
  • Pogosto so problemi taki, da se, če želimo zmanjšati časovno zahtevnost, poveča prostorska zahtevnost in obratno.
0%
0%