7. tēma: Algoritmi. 3. stunda: Big O un Sarežģītība.

Tavs šīs stundas izaicinājums: Tu proti uzrakstīt kodu, kas strādā, bet vai tas strādā labi? Šodien mēs iemā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.

Teorija: Kas ir Big O?

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. Līmenis (Vienkāršs): "Konstantais ātrums — O(1)"

Pierādīsim, ka O(1) darbības prasa vienādu laiku neatkarīgi no datu apjoma.

1. Failā big_o.py importē time bibliotēku.
2. Izveido funkciju iegut_pirmo(dati), kas atgriež saraksta elementu ar indeksu [0].
3. Izsauc to divreiz: vienreiz ar sarakstu, kurā ir 10 elementi, otreiz – ar 10 000 000 elementiem.
4. Nomēri un izdrukā laiku abiem izsaukumiem.

import time

def iegut_pirmo(dati):
    return dati[0]

mazs_saraksts = list(range(10))
liels_saraksts = list(range(10000000))

# Mērām mazam
sakums = time.time()
iegut_pirmo(mazs_saraksts)
laiks_mazam = time.time() - sakums

# Mērām lielam
sakums = time.time()
iegut_pirmo(liels_saraksts)
laiks_lielam = time.time() - sakums

print(f"O(1) laiks mazam sarakstam: {laiks_mazam:.7f}s")
print(f"O(1) laiks milzīgam sarakstam: {laiks_lielam:.7f}s")

2. Līmenis (Viduvējs): "Lineārais O(n) pret Kvadrātisko O(n²)"

Apskatīsim, cik reāli soļus dators veic atkarībā no uzrakstīto ciklu daudzuma.

1. Pievieno failam divus mainīgos: soli_n = 0 un soli_n2 = 0.
2. Izveido vienu parastu for ciklu no 0 līdz 100, kas katrā solī palielina soli_n par 1.
3. Izveido iegulto ciklu (cikls ciklā), kur abi iet no 0 līdz 100, un palielini soli_n2 par 1.
4. Izdrukā abu mainīgo beigu vērtības.

elementu_skaits = 100

soli_n = 0
# O(n) - Lineārs algoritms
for i in range(elementu_skaits):
    soli_n += 1

soli_n2 = 0
# O(n^2) - Kvadrātisks algoritms
for i in range(elementu_skaits):
    for j in range(elementu_skaits):
        soli_n2 += 1

print(f"Datu apjoms: {elementu_skaits}")
print(f"O(n) soļu skaits: {soli_n}")
print(f"O(n^2) soļu skaits: {soli_n2}")

3. Līmenis (Padziļināts): "Koda analītiķis"

Tavs uzdevums kā inženierim ir nolasīt kodu un uzreiz saprast tā sarežģītību.

1. Pārkopē zemāk esošos trīs funkciju fragmentus savā Python failā.
2. Virs katras funkcijas pievieno komentāru (#), kurā norādi tās Big O notāciju (piem., O(1), O(n), O(n²)).
3. Komentārā ar vienu teikumu pamato savu atbildi.

# 1. Analīze
# Tava atbilde: O(...) jo ...
def dzes_pedejo(dati):
    dati.pop()

# 2. Analīze
# Tava atbilde: O(...) jo ...
def aprekinat_kopejo_rezultatu(punkti):
    summa = 0
    for punkts in punkti:
        summa += punkts
    return summa

# 3. Analīze
# Tava atbilde: O(...) jo ...
def meklet_dublikatus(dati):
    for i in dati:
        for j in dati:
            if i == j:
                print("Atrasts dublikāts!")