Programmēšana I - 7. tēma · 6 stundas

Algoritmi un // to efektivitāte

Kā dators atrod vienu vārdu starp miljoniem? Apgūsti bināro meklēšanu, kārtošanas algoritmus un Big O notāciju - rīkus, kas palīdz prognozēt, vai kods darbosies ātri ar miljoniem ierakstu.

› Sākt tēmu Noslēguma projekts →

6 stundas meklēšana kārtošana Big O

prog1_7/algoritmi.py

● algoritmi.py big_o.py

1 2 3 4 5 6 7 8 9 10 11 12 13

# Binārā meklēšana def bināra_meklēšana(saraksts, mērķis): kreisais, labais = 0, len(saraksts)-1 while kreisais <= labais: vidus = (kreisais + labais) // 2 if saraksts[vidus] == mērķis: return vidus elif saraksts[vidus] < mērķis: kreisais = vidus + 1 else: labais = vidus - 1 return -1 # Nav atrasts

● gatavs Python 3.12 UTF-8 Ln 13, Col 1

O(log n) ātrums kārtošanas algoritmi Big O notācija

# 01 stundas

Tēmas saturs - 6 stundas

No lineārās meklēšanas līdz Big O - katru jēdzienu apgūsti ar praktisku kodu.

noslēguma projekts →

// meklēšana.py

O(n) vs O(log n)meklēšana

Meklēšanas pamati

Lineārā pret bināro meklēšanu - kāpēc binārā ir neticami ātra kārtotā masīvā.

1. stundaatvērt ↗

// kartosana.py

bubble sort · selection sortkārtošana

Kārtošanas loģika

Bubble sort un selection sort - kā dators sakārto datus un cik daudz darba tas prasa.

2. stundaatvērt ↗

// big_o.py

Big O · time complexitysarežģītība

Big O un Sarežģītība

Četras sarežģītības klases grafikā - O(1), O(log n), O(n), O(n²) un to praktiskā nozīme.

3. stundaatvērt ↗

// atrums.py

sorted() · timeitiebūvētās

Iebūvēto funkciju ātrums

Python iebūvētās funkcijas pret rokraksta algoritmiem - mēra ar timeit.

4. stundaatvērt ↗

// pipeline.py

map · filter · lambdafunkcionālā

Iebūvēto funkciju efektivitāte

map(), filter() un reduce() - datu apstrādes pipeline funkcionālā stilā.

5. stundaatvērt ↗

$ python koda_lauzejs.py

Python · algoritmiprojekts

Noslēguma projekts: Koda lauzējs

Dators ar bināro meklēšanu min skaitli, skaita mēģinājumus un pamana pretrunas.

6. stunda · projektsatvērt ↗

# 02 špikeris

7. tēmas špikeris

Ātrā uzziņa - algoritmi, Big O tabula un iebūvētās funkcijas.

visi špikeļi →

prog1_7/špikeris.py

● meklēšana big_o sorted()

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

# Lineārā meklēšana - O(n) def lineārā(s, m): for i, v in enumerate(s): if v == m: return i return -1 # Bubble sort - O(n²) for i in range(len(s)): for j in range(len(s)-i-1): if s[j] > s[j+1]: s[j], s[j+1] = s[j+1], s[j] # Big O tabula: # O(1) - konstants (masīva elements pēc indeksa) # O(log n) - logaritmisks (binārā meklēšana) # O(n) - lineārs (lineārā meklēšana) # O(n log n) - (Python sorted(), merge sort) # O(n²) - kvadrātisks (bubble sort) # sorted() ar key parametru sorted(vārdi, key=lambda x: len(x)) # timeit - mēra izpildes laiku import timeit timeit.timeit("sorted([3,1,2])", number=10000)

● špikeris Python 3.12 UTF-8

› vidus = (l + r) // 2 # binārā meklēšana - O(log n)

› Sākt 1. stundu Noslēguma projekts →