Č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 O(n), drugi pa O(n).

  • 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 5x, pri kvadratičnem pa 25x.

Kaj nam pove časovna zahtevnost?

  • Imamo algoritem, za katerega vemo, da je njegova časovna zahtevnost O(n).
  • 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
      • 3x večji problem - 3x 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
      • 9x večji problem - 9x dlje, torej cca 45 sekund

Kaj nam torej pove časovna zahtevnost?

  • Imamo algoritem, za katerega vemo, da je njegova časovna zahtevnost O(n2).
  • 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:

      • 3x večji problem - 9x (32 x) dlje, torej cca 45 sekund

  • Kaj pa problem velikosti 1000?

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

Kaj nam pove časovna zahtevnost?

  • Seveda smo pri obeh primerih HUDOOOO poenostavili
  • Dva algoritma

  • Dejanska čas. zahtevnost naj bo

    • T1(n) = n – 95
    • T2(n) = n / 100 + 4
  • Oba O(n)
  • T1(100) = 5, T2(100) = 5
  • T1(300) = 205, T2(300) = 12
  • T1(900) = 805, T2(900) = 13
  • T1(1800) = 1705, T2(1800) = 22
  • T1(3600) = 3505, T2(3600) = 40
  • T1(7200) = 7105, T2(7200) = 76
  • T1(14400) = 14305, T2(14400) = 148
  • Č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 2x, 10x, 100x večji (ima toliko več podatkov)

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

    • Če se 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 (O(n)), pričakujemo da bo čas izvajanja na istem računalniku 4x, 100x, 10000x daljši.

    • Če se 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 (O(2)), pričakujemo da bo čas izvajanja na istem računalniku 4x, 1000x, 1267650600228229401496703205376x 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 O notacijo
  • O(n)
  • V O(n) se skrivajo najrazličnejše funkcije – n/10000 – 100n -50, 1000n ... – vse take, kjer od nekega n naprej na vrednost bistveno vpliva le še n.
  • Zato z O notacijo pravzaprav govorimo le o rasti časa (v odvisnosti od velikosti problema) – torej o tem, kaj se bo dogajalo s časom, če bomo vzeli 2x, 5x, 10x 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 (5x večji problem, 5x več časa)
  • Nikakor pa to ne pomeni, da se bo npr. problem velikosti 100 pri linearnem algoritmu izvajal 100 sekund (ali pa potreboval 100 x čas osnovne operacije)
  • Lahko pa pričakujemo, da če vemo, da je algoritem linearne časovne zahtevnosti in bomo vzeli 3x večji problem, da se bo ta verjetno reševal 3x 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

    • T(n) = .....
    • n: velikost problema
    • Točne formule (funkcije) se običajno ne da napisati (prezapletena, povezana z verjetnostjo ...)
    • Zato naredimo oceno in vse izrazimo kar z O notacijo.
  • Zavedati se je potrebno, da gre za oceno in da je zaradi O 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%