• Algoritem je postopek, ki nam korak za korakom pove, kako rešiti dani problem
• Za dani problem v splošnem obstaja veliko algoritmov, ki določijo postopek, s katerim rešimo problem

• Npr. obstaja veliko algoritmov za izračun produkta dveh števil:

  • Tabela poštevanke (primerno le za majhna števila)
  • Pisno množenje
  • Množenje z uporabo logaritmov.
  • Uporaba računala.
  • Uporaba postopkov vgrajenih v računalnik.
  • Leibnitzov "računalnik"
  • ...

• navodilo, kako opraviti določen postopek
• KAJ storiti, KAKO to storiti
• Končno zaporedje ukazov, ki, če jih ubogamo, opravijo neko nalogo

• Podatkovna struktura je sistematični način kako organizirati skupino podatkov.
• Statična podatkovna struktura je taka, katere velikost je dokončno določena ob nastanku. Npr. tabela
• Dinamična podatkovna struktura je taka, katere velikost se lahko spreminja (povečuje/zmanjšuje) – npr. povezani seznami, dvojiško drevo, ...
• Za vsako podatkovno strukturo potrebujemo postopke za vstavljanje, brisanje, iskanje in podobno.

• Je vreča, kamor shranjujemo podatke
• Vanjo dajemo in iz nje jemljemo
• Glede na značilnosti tega kakšen podatek dobimo iz vreče (in tudi glede na to kaj mora vreča početi, da nam tak podatek vrne) ločimo različne PS.

• Sklad

  • Iz vreče vedno potegnemo tisti podatek, ki je najmanj časa v vreči

• vrsta

  • Iz vreče vedno potegnemo tisti podatek, ki je najdalj časa v vreči

• Drevo

  • Podatki so urejeni po hierarhiji (nadrejeni/podrejeni)
  • Vedno dobimo le glavnega

• Tabela

  • Podatke dobivamo iz vreče glede na indekse

• Verižni seznam

  • Vsak podatek ve, kje je njegov naslednik (in nič več)
• ...

• Za dani problem imamo več algoritmov – kateri je "najboljši"?
• Koliko časa dani algoritem zahteva?

• Koliko prostora (pomnilnika) dani algoritem zahteva?

  • Zanima nas dodaten prostor (poleg tistega, ki ga potrebujemo za podatke in rezultat)

    • Slednje tako ali tako potrebujejo vsi algoritmi

  • Čeprav pogosto zanemarjeno, pa je količina dodatnega pomnilnika pogosto zelo pomembna

    • Največ računalnikov ima zelo omejen prostor (računalniki v hišnih napravah, avtomobilih, strojih ...)
• V splošnem je tako časovna kot prostorska zahtevnost odvisna od podatkov za dani algoritem (tipično od "velikosti" vhodnih podatkov).

• Čas meriti v sekundah izvajanja programa?

  • + enostavno

  • – odvisno od jezika, prevajalnika in procesorja.

    • Nemogoče primerjati različne algoritme (razen, če bi imeli možnost izvesti vse na istem računalniku, z istim jezikom, z istim prevajalnikom)

• Šteti karakteristične operacije?

  • (npr. aritmetične operacije v matematičnih algoritmih, primerjave v iskalnih algoritmih, ...)
  • + odvisno le od algoritma, nič od strojne opreme, učinkovitosti prevajalnika, izbranega jezika, uspešnosti kodiranja, meri dejansko učinkovitost algoritma
  • - običajno zapleteno

• T(n) = 5n2 – 2n + 20

  • Formula, ki nam pove, kako se spreminja čas (število karakterističnih operacij) v odvisnosti od velikosti problema

  • Če rešujemo problem velikosti n, bomo potrebovali 5n2 – 2n + 20 karakterističnih operacij

    • 500 za problem velikosti 10
    • 7980 za problem velikosti 20
    • ...

• Na računalniku A algoritem X reši problem velikosti n v treh minutah
• Isti program, a z 10x več podatki, izvedemo na istem računalniku. Kaj lahko napovemo glede časa izvajanja?
• Isti program z istimi podatki izvedemo na 1000x hitrejšem računalniku. Kaj lahko napovemo glede časa izvajanja?
• Na računalniku B algoritem Y reši isti problem velikosti n v dveh minutah. Je računalnik B hitrejši od računalnika A? Je algoritem X slabši od algoritma Y?
• Na računalniku A izvedemo algoritem X na n podatkih. Izvajanje traja dve uri. Na računalniku A izvedemo algoritem Y na n podatkih. Izvajanje traja dve uri in pol. Je algoritem X boljši od algoritma Y? Kaj se bo zgodilo, če zgodbo ponovimo na problemu s 100x več podatki?

• Z merjenjem časa dejansko ne zvemo nič!

• Težja
• Natančnejša od meritev
• Da nam RAZUMEVANJE, zakaj določen algoritem potrebuje ta čas
• Vidimo “kritične” dele
• Pogosto iz analize dobimo ideje za izboljšave

• količina sredstev, ki jih potrebujemo za rešitev problema

  • Časovna: Število karakterističnih operacij
  • Prostorska: Število dodatnih spremenljivk (če smo natančnejši – število zlogov pomnilnika)
• odvisnost od obsežnosti (velikosti) problema
• kaj meriti

• pogosto le ocenimo zahtevnost

  • Točna funkcija nas NE zanima

  • Zanima nas rast

    • Kaj se zgodi, če velikost reševanega problema povečujemo
  • T1(n) = 5n – 2n + 20
  • T2(n) = n/100 + 5n + 20
  • T3(n) = 1000000 n - 5000n + 1

  • Za dovolj velike n se T1, T2, T3 obnašajo podobno

    • enako rastejo
    • kot funkcija n

• red velikosti

  • O notacija
  • O(n)

• Algoritem zahtevnosti O(log n) je boljši kot algoritem zahtevnosti O(n), ker je log n za vse vrednosti n od nekje naprej (od dovolj velikega n) zagotovo manjše kot n. O(log n) pomeni počasnejšo rast kot O(n).
• Kompleksnost O(X) pomeni “reda X”, t.j., rast sorazmerno z X. X označuje red rasti, kjer zanemarimo počasneje rastoče člene in konstantne faktorje.

Nekaj značilnih časovnih zahtevnosti:

(predpostavimo, da je zahtevnost točno taka in ne le tega reda)

• 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?

  • Ker je rast časa za ta algoritem linearna

  • 3x večji problem - 3x dlje, torej cca 15 sekund

    • V splošnem to ni nujno čisto res (ne vemo, ali smo že dosegli tisto velikost problema, ko "zanemarjeni" členi (ki jih je "pojedla" O notacija) ne delajo "zgage")

• Kaj pa problem velikosti 900?

  • Ker je rast časa za ta algoritem linearna
  • 9x večji problem - 9x dlje, torej cca 45 sekund
• Vsekakor pa od neke velikosti problema dalje zagotovo vemo, da bomo pri reševanju 5x večjega problema čakali na rešitev približno 5x dlje.

• 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?

  • Ker je rast časa za ta algoritem kvadratična
  • 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 - 100x dlje, torej cca 500 sekund

• 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.

• 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.