Silmukoiden ja sisäkkäisten silmukoiden analysointi
Laskekaa yksittäisten silmukoiden, sisäkkäisten silmukoiden ja pienenevillä alueilla toimivien silmukoiden, kuten binäärihaun tai kolmiosilmukoiden, aikavaativuus.
Silmukoiden ja sisäkkäisten silmukoiden analysointi on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Yksi silmukka: O(n)
Yksinkertaisin silmukka suorittaa runkonsa n kertaa, joten sen vaativuus on O(n). Suurempi askel muuttaa suoritusmäärää, mutta ei vaativuusluokkaa. Aloittakaa aina laskemalla, kuinka monta kertaa runko suoritetaan. Katso koodi.
# O(n): body runs n times
def count_ops_linear(n):
ops = 0
for i in range(n):
ops += 1 # constant work
return ops
print(count_ops_linear(100)) # 100
# Still O(n): step=2 halves count but same class
def count_ops_half(n):
ops = 0
for i in range(0, n, 2):
ops += 1
return ops
print(count_ops_half(100)) # 50 => O(n)Sisäkkäiset silmukat: O(n²) ja enemmän
Kaksi sisäkkäistä silmukkaa, jotka käyvät kumpikin n kertaa, tuottavat n x n = O(n^2); kolme silmukkaa tuottaa O(n^3). Jos sisempi silmukka suoritetaan kiinteän määrän kertoja, kokonaisuus pysyy kuitenkin lineaarisena.
def count_pairs(n):
ops = 0
for i in range(n): # n iterations
for j in range(n): # n iterations each
ops += 1
return ops
print(count_pairs(10)) # 100 = 10^2
print(count_pairs(100)) # 10000 = 100^2
# Doubling n quadruples ops: classic O(n^2)Kolmiosilmukka: O(n²/2) = O(n²)
Kun sisempi silmukka alkaa kohdasta i+1, suorituskerrat muodostavat kolmion: n(n-1)/2, joka on puolikkaan pois jättämisen jälkeenkin O(n^2). Kaikkien yksilöllisten parien ongelmat näyttävät tältä.
def count_unique_pairs(n):
ops = 0
for i in range(n): # n iterations
for j in range(i+1, n): # n-1, n-2, ..., 0
ops += 1
return ops
print(count_unique_pairs(10)) # 45 = 10*9/2
print(count_unique_pairs(100)) # 4950
# Still O(n^2) -- constant factor 1/2 droppedPienenevän alueen silmukka: O(log n)
Kun silmukkamuuttuja puolitetaan jokaisella askeleella, vaativuudeksi saadaan O(log n). Olennainen kysymys on: pieneneekö alue kertoimella (log n) vai vakioaskelin (n)? Katso koodi.
def count_log_ops(n):
ops = 0
i = n
while i >= 1:
ops += 1
i //= 2 # halve each iteration
return ops
import math
for n in [8, 16, 64, 1024]:
ops = count_log_ops(n)
print(f'n={n}, ops={ops}, log2={int(math.log2(n))}')
# ops tracks log2(n) closelySisäkkäinen silmukka, jonka sisempi silmukka pienenee: O(n log n)
n kertaa suoritettava ulompi silmukka ja O(log n):n sisempi silmukka tuottavat vaativuuden O(n log n) — tämä on merge sortin rakenne. O(log n):n sisäisen vaiheen tunnistaminen on lajittelujen analysoinnin avain.
import math
def count_n_log_n(n):
ops = 0
for i in range(n): # n iterations
j = n
while j >= 1: # log n iterations
ops += 1
j //= 2
return ops
for n in [8, 32, 128]:
ops = count_n_log_n(n)
predicted = int(n * math.log2(n))
print(f'n={n}: actual={ops}, n*log2(n)~={predicted}')Riippuvat sisemmät silmukat
Kun sisemmän silmukan alue riippuu ulomman silmukan indeksistä, laskekaa kokonaismäärä, ei määrää vaihetta kohti. Kun sisempi silmukka käy alueen 0..i läpi, summa on n(n-1)/2 = O(n^2). Katso koodi.
# Inner loop runs i times: total = 0+1+2+...+(n-1) = n(n-1)/2 => O(n^2)
def sum_inner_i(n):
ops = 0
for i in range(n):
for j in range(i): # runs 0,1,2,...,n-1 times
ops += 1
return ops
print(sum_inner_i(10)) # 45 = 10*9/2 => O(n^2)
# Inner loop runs n/i times (i doubles): sum ≈ n*log n => O(n log n)
def sum_inner_n_over_i(n):
ops = 0
i = 1
while i <= n:
for j in range(n // i):
ops += 1
i *= 2
return ops
print(sum_inner_n_over_i(64)) # ~ 64*6 = 384Kuplalajittelun analysointi vaihe vaiheelta
Kuplalajittelu tekee n(n-1)/2 vertailua, joten sen vaativuus on O(n^2). Vaikka käytössä olisi aikainen lopetus, käänteisessä järjestyksessä oleva syöte vaatii silti jokaisen vertailun. Menetelmä on liian hidas suurille syötteille.
def bubble_sort(arr):
n = len(arr)
comparisons = 0
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # early exit if sorted
break
return comparisons
arr = list(range(10, 0, -1)) # worst case: reversed
ops = bubble_sort(arr)
print(f'Sorted: {arr}')
print(f'Comparisons: {ops}') # 45 = 10*9/2Merkkijonojen ja osamerkkijonojen läpikäynti
Varokaa tätä: Pythonin slicing on O(k), eikä siis ilmaista, ja merkkijonojen yhdistäminen +-operaattorilla silmukassa on O(n^2), koska merkkijono kopioidaan joka kerta. Käyttäkää sen sijaan ''.join(parts). Katso koodi.
# O(n^2): string concat in loop
def build_bad(n):
s = ''
for i in range(n):
s += str(i) # copies s each time!
return s
# O(n): join is a single pass
def build_good(n):
parts = []
for i in range(n):
parts.append(str(i))
return ''.join(parts)
print(build_good(10)) # '0123456789'Useita syöteparametreja
Kahden syötteen tapauksessa vaativuudessa voidaan tarvita molempia: erillinen työ tuottaa O(m + n) ja sisäkkäinen työ O(m x n). Graafien vaativuus ilmoitetaan usein muodossa O(V + E). Nimetkää jokainen muuttuja selkeästi.
# O(m + n): two independent loops
def independent(m, n):
a = sum(range(m)) # O(m)
b = sum(range(n)) # O(n)
return a + b # total O(m + n)
# O(m * n): nested
def nested(m, n):
count = 0
for i in range(m): # O(m)
for j in range(n): # O(n) each
count += 1
return count # O(m * n)
print(independent(5, 10)) # 10 + 45 = 55
print(nested(5, 10)) # 50Sisäkkäisyys ja peräkkäiset kutsut
Funktiokutsu ei ole maksuton — myös sen sisällä oleva silmukka on laskettava mukaan. Jos kutsutte O(n)-apuohjelmaa n kertaa, vaativuudeksi tulee O(n^2). Katsokaa analysoidessanne aina myös mustien laatikoiden sisälle.
# Naive string matching: O(n*m)
def naive_search(text, pattern):
n, m = len(text), len(pattern)
matches = []
for i in range(n - m + 1): # O(n)
if text[i:i+m] == pattern: # O(m) comparison + O(m) slice
matches.append(i)
return matches
# Total: O(n*m)
print(naive_search('abcabcabc', 'abc')) # [0, 3, 6]Käytännössä: tunnistakaa vaativuus nopeasti
Muodostakaa tapa: laskekaa silmukoiden sisäkkäisyys, tarkistakaa, riippuuko sisempi silmukka ulommasta, ja huomioikaa funktiokutsuihin ja slicingiin kätkeytyvät kustannukset. Koodi on pulma kokeiltavaksi.
# What is the complexity of this function?
def mystery(nums):
result = []
for i in range(len(nums)): # O(n)
for j in range(i, len(nums)): # O(n) worst
if sum(nums[i:j+1]) == 0: # O(n) slice + sum!
result.append((i, j))
return result
# Answer: O(n^3) -- three nested n-proportional ops
# Outer O(n) x inner O(n) x sum/slice O(n) = O(n^3)Pikatesti
Pikatesti — katsotaan, kuinka hyvin silmukka-analyysin niksit jäivät mieleen. Luottakaa tässä päättelyynne. 💪
Oppitunnin yhteenveto
Yhteenveto: sisäkkäiset silmukat kertautuvat ja erilliset summautuvat, puolittuva sisempi silmukka tuottaa O(n log n):n, ja myös kutsujen ja slicingin piilevät kustannukset on laskettava mukaan.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Silmukoiden ja sisäkkäisten silmukoiden analysointi” ilmainen?
Kyllä – oppitunnin ”Silmukoiden ja sisäkkäisten silmukoiden analysointi” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Silmukoiden ja sisäkkäisten silmukoiden analysointi”?
Laskekaa yksittäisten silmukoiden, sisäkkäisten silmukoiden ja pienenevillä alueilla toimivien silmukoiden, kuten binäärihaun tai kolmiosilmukoiden, aikavaativuus. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Silmukoiden ja sisäkkäisten silmukoiden analysointi”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Big-O-notaatio alusta alkaen
- Silmukoiden ja sisäkkäisten silmukoiden analysointi
- Rekursio ja rekursiopuumenetelmä
- Tilavaativuus ja kompromissit