ebSkola

7. tēma / 7.3

7.3 Big O un Sarežģītība

Stundas uzdevums: Tu proti uzrakstīt kodu, kas strādā, bet vai tas strādā labi? Mācīsimies skatīties uz kodu kā profesionāli inženieri, izmantojot Big O notāciju, lai paredzētu programmas uzvedību, kad tai jāapstrādā nevis desmit, bet desmit miljoni datu vienību.

SR 2.4.16. (Tu novērtē algoritmu sarežģītību un efektivitāti dažādos izpildes apstākļos)

70 min plāns: Teorija un paraugs (~10 min) · 1. uzdevums (~15 min) - izmēri O(1) darbību · 2. uzdevums (~25 min) - salīdzini O(n) ar O(n²) · 3. uzdevums (~20 min) - nosaki sarežģītību svešam kodam. Papildu uzdevumu sāc tikai tad, ja pārējie trīs ir gatavi.

Pirms sāc: atver VS Code un izveido failu big_o.py. Laiku mērīsi ar time bibliotēku, bet secinājumus izdarīsi par soļu skaitu, nevis sekundēm.

Teorija: Kas ir Big O?

  • Kāpēc nemērīt sekundēs? Katrs dators ir atšķirīgs. Sekundes neko neizsaka par pašu algoritmu. Tā vietā mēs mēram, kā pieaug veikto operāciju (soļu) skaits, palielinoties datu apjomam (n).
  • Galvenās Big O klases:
    • O(1) - Konstants laiks: Zibensātrs. Cik datu, nav svarīgi. Piemērs: paņemt saraksta pirmo elementu (saraksts[0]).
    • O(log n) - Logaritmisks laiks: Ļoti ātrs. Dati ar katru soli tiek dalīti uz pusēm. Piemērs: Binārā meklēšana.
    • O(n) - Lineārs laiks: Pieaug proporcionāli datu apjomam. 100 elementi = 100 soļi. Piemērs: Lineārā meklēšana, viens for cikls.
    • O(n²) - Kvadrātisks laiks: Lēns. Katram elementam jāpārbauda katrs cits elements. 100 elementi = 10 000 soļi. Piemērs: Burbuļkārtošana, divi iegulti for cikli.

Vides sagatavošana (Windows)

  1. Atver PowerShell.
  2. Ieej algoritmu mapē: cd Tema7_Algoritmi
  3. Izveido jaunu failu un atver to kodu redaktorā: ni big_o.py; code big_o.py

Praktiskie uzdevumi

1. uzdevums -

Izmēri O(1) darbību

Beigās tu redzēsi, ka daži darbi neatkarīgi no datu apjoma aizņem vienādu laiku.

  1. Ieraksti import time.
  2. Uzraksti funkciju def iegut_pirmo(dati):, kas atgriež dati[0].
  3. Izveido sarakstu ar 10 elementiem un otru ar 1 000 000 elementiem.
  4. Izmēri laiku ar sakums = time.time() pirms un pēc izsaukuma.
  5. Izdrukā abus laikus.
  6. Pieraksti, vai lielākais saraksts prasīja manāmi vairāk laika.

Gatavs, kad: abi laiki ir gandrīz vienādi, lai gan viens saraksts ir 100 000 reižu lielāks.

2. uzdevums -

Salīdzini O(n) ar O(n kvadrātā)

Beigās tu redzēsi, cik strauji aug ligzdota cikla laiks.

  1. Uzraksti funkciju ar vienu ciklu, kas saskaita visus saraksta elementus.
  2. Uzraksti otru funkciju ar diviem ligzdotiem cikliem pār to pašu sarakstu.
  3. Palaid abas ar 100 elementiem un pieraksti laikus.
  4. Palaid abas ar 1000 elementiem un pieraksti laikus.
  5. Izrēķini, cik reižu pieauga katras funkcijas laiks.
  6. Pieraksti, kura funkcija palēninājās vairāk.

Gatavs, kad: palielinot datus 10 reizes, viena cikla laiks aug ~10 reizes, bet ligzdotā - ~100 reizes.

3. uzdevums -

Nosaki sarežģītību svešam kodam

Beigās tu pratīsi paskatīties uz kodu un pateikt tā Big O.

  1. Uzraksti trīs īsas funkcijas: vienu ar saraksts[0], vienu ar vienu ciklu, vienu ar diviem ligzdotiem.
  2. Pieraksti katrai savu minējumu: O(1), O(n) vai O(n²).
  3. Pievieno katrai skaitītāju, cik operāciju tā veic.
  4. Palaid katru ar 10 un ar 100 elementiem.
  5. Salīdzini skaitītāja vērtības ar saviem minējumiem.
  6. Izlabo minējumu, ja skaitļi to neapstiprina.
  7. Pieraksti vienu secinājumu: kāpēc Big O nemēra sekundēs.

Gatavs, kad: visiem trim gadījumiem tavs minējums sakrīt ar izmērīto operāciju skaita pieaugumu.

Papildu uzdevums - Atrodi O(log n)

Ja pamatdarbs ir gatavs, izmēri bināro meklēšanu no 7.1 stundas.

  1. Nokopē savu binary_search funkciju no 7.1 stundas.
  2. Pievieno tai soļu skaitītāju, ja tā vēl nav.
  3. Palaid ar 100, 1000 un 10 000 elementiem.
  4. Pieraksti soļu skaitu katrā gadījumā.
  5. Pieraksti, par cik soļiem pieauga rezultāts, kad dati pieauga 10 reizes.

Gatavs, kad: dati pieaugot 10 reizes, soļu skaits pieaug tikai par dažiem - tā izskatās O(log n).

Koda piemērs (O(n) pret O(n²) mērījums - grūtākā daļa)

import time

# Grūtākā vieta: saprast, ka svarīgs nav SEKUNŽU skaits,
# bet tas, CIK REIZES laiks pieaug, kad dati pieaug 10 reizes.

def viens_cikls(dati):          # O(n)
    kopa = 0
    for x in dati:
        kopa += x
    return kopa

def divi_cikli(dati):           # O(n kvadrātā)
    skaits = 0
    for x in dati:
        for y in dati:
            skaits += 1
    return skaits

for n in (100, 1000):
    dati = list(range(n))

    t0 = time.time(); viens_cikls(dati); t1 = time.time()
    t2 = time.time(); divi_cikli(dati);  t3 = time.time()

    print(f"n={n:5}  O(n)={t1-t0:.5f}s   O(n^2)={t3-t2:.5f}s")
Palielinot n no 100 uz 1000 (10 reizes), O(n) funkcijas laiks pieaug aptuveni 10 reizes, bet O(n²) funkcijas laiks - aptuveni 100 reizes. Tieši šī attiecība, nevis pati sekunžu vērtība, ir Big O jēga.