• Za neko delnico smo določeno obdobje spremljali gibanje njene cene. Zanima nas v katerem obdobju smo lahko s to delnico zaslužili največ. Delnico kupimo in prodamo le enkrat.
• Pozitivni podatek pomeni, da je cena delnice zrasla, negativni pa, da je padla

• Denimo, da so podatki:

  • 12, 3, 5, -10, -8, 7, 11, -30, 6, 8, -40
  • Če bi delnico npr. kupili na začetku 1 dne in jo na začetku 2 dne prodali, bi zaslužili 12, če pa bi jo prodali na začetku 5. dne, bi zaslužili 10 (12 + 3 + 5 -10) . Če bi jo kupili na začetku 5. dne in jo prodali na začetku 7. dne, bi bil “zaslužek” – 1 (-8 + 7).

  • Rešitev za ta problem je:

    • Zaslužek 20
    • Dosežemo ga lahko 2x
    • Kupimo 1. dan (na začetku dneva) in prodamo na začetku 4. dneva
    • Kupimo 1. dan (na začetku dneva) in prodamo na začetku 9. dneva

• Denimo, da so podatki

• Rešitev za ta problem je:

  • Zaslužek 30
  • Kupimo 4. dan (na začetku dneva) in prodamo na začetku 12. dneva

• Dano je zaporedje celih števil a1, a2, …, an. Naj bo
• Poišči S = maksimalna vsota

• 8, -6, 10, -14, 13, -5, 7, -9, 18, -3, 2

  • rešitev 13, -5, 7, -9, 18 (24)

• Velikost problema

  • število podatkov (n)

• Tipične operacije za problem:

  • seštevanja
  • ? Primerjanje ?

• Število primerjanj:

  • i = 1: n primerjanj
  • i = 2: n – 1 primerjanj
  • ....
  • Skupaj: n + (n – 1) + (n – 2) + ... + 2 + 1
  • n * (n + 1) / 2
  • O (n)

Število seštevanj:

• i = 1

  • Konec

    • j = 1: 0 seštevanj
    • j = 2: 1 seštevanje
    • ...
    • j = n: n - 1 seštevanj
  • Skupaj: 0 + 1 + ... + n – 1 = n * (n – 1) / 2

• i = 2

  • Konec

    • j = 2: 0 seštevanj
    • j = 3: 1 seštevanje
    • ...
    • j = n: n - 2 seštevanj
  • Skupaj: 0 + 1 + ... + n – 2 = (n – 1) * (n – 2) / 2

• i = m

  • Konec

    • j = m: 0 seštevanj
    • j = m + 1: 1 seštevanje
    • ...
    • j = n: n – m seštevanj
  • Skupaj: 0 + 1 + ... + n – m = (n – m) * (n – m + 1) / 2

• i = n - 1

  • Skupaj: 1

• i = n

  • Skupaj: 0

Skupaj: (n * (n – 1) + (n – 1) * (n – 2) + ... + 1 * 2)/ 2 = n3 + ...

O(n)

• Ko računamo vsoto od a do a smo na prejšnjem koraku ravno izračunali vsoto od a do a
• Prej – staro vsoto "pozabili"
• Sedaj - uporabimo prejšnjo vsoto!

• i = 1

  • Primerjanj: n
  • Seštevanj: n – 1

• i = 2

  • Primerjanj: n - 1
  • Seštevanj: n – 2
• ...

• i = m

  • Primerjanj: n – m + 1
  • Seštevanj: n – m
• n – 1 + n – 2 + ... + 2 + 1
• n (n – 1)/2
• O(n)

• 8, -6, 10, -14, 13, -5, 7, -9, 18, -3, 2
• Odločamo se, ali vzeti zraven ai
• Začnemo z 0
• Ali bi k vsoti vzeli a1?
• Da, če je pozitiven!
• Do sedaj vsota 0 (če a1 neg.) oziroma a1!
• Ali bi k vsoti vzeli a2?

• Če je pozitiven – vsekakor

  • Vsota od prej + a2 + vsota še naprej (ki je vsaj 0)

• Če je negativen – morda

  • Morda se ga splača uporabiti kot "most" med vsoto levo in morebitno vsoto desno?

  • Kdaj:

    • če je vsota prej + a2 še večja kot 0 (sicer se bolj splača začeti znova z 0)
• Ko smo sprejeli to odločitev, vemo, koliko je vredna optimalna vsota, ki se konča pri 2
• Ponavljamo!

• 8, -6, 10, -14, 13, -5, 7, -9, 18, -3, 2

• Algoritem A: O(n)
• Algoritem B: O(n)
• Algoritem C: O(n)

• Izmerimo, če bo to res

• Generiramo naključno gibanje cene delnice

• Kako do naključnega števila med a in b?

  • Interval [0,1) /random.random() / raztegnemo na [0, (b – a + 1)) / * (b – a + 1) /
  • Premaknemo za a /+a/ : [a, b + 1)
  • Odrežemo decimalke /int/– {a, a+1, a+2 … b – 1, b}

def nakStev(a, b):
   ''' naključno celo število med a in b (vključno) '''
   return a + int((b - a + 1) * random.random())

for velPoskusa in [10, 20, 40, 80, 160, 320, 640, 1280] :
    gibanjeDelnice = /
        [nakStev(-100, 100) for i in range(velPoskusa + 1)]
    izpišiČase(gibanjeDelnice)

• Kaj pričakujemo?
• Kakšna bodo razmerja med števili v prvem, drugem in tretjem stolpcu?