Analiza pętli i pętli zagnieżdżonych
Obliczą Państwo złożoność czasową pojedynczych pętli, pętli zagnieżdżonych oraz pętli ze zmniejszającymi się zakresami, takich jak wyszukiwanie binarne lub iteracje po trójkącie.
Analiza pętli i pętli zagnieżdżonych to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Pojedyncza pętla: O(n)
Najprostsza pętla wykonuje swoje ciało n razy, więc ma złożoność O(n). Większy krok zmienia liczbę iteracji, ale nie klasę złożoności. Analizę zawsze należy rozpocząć od policzenia, ile razy wykonywane jest ciało pętli. Zobacz kod.
# 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)Pętle zagnieżdżone: O(n²) i więcej
Dwie zagnieżdżone pętle, z których każda wykonuje się n razy, dają n x n = O(n^2); trzy dają O(n^3). Jeśli jednak pętla wewnętrzna wykonuje stałą liczbę iteracji, całość nadal ma złożoność liniową.
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)Pętla trójkątna: O(n²/2) = O(n²)
Gdy pętla wewnętrzna zaczyna się od i+1, liczba iteracji tworzy trójkąt: n(n-1)/2, co po pominięciu połowy nadal daje O(n^2). Tak wyglądają problemy dotyczące wszystkich unikalnych par.
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 droppedPętla ze zmniejszającym się zakresem: O(log n)
Gdy zmienna sterująca pętlą jest dzielona przez połowę w każdym kroku, otrzymujemy O(log n). Kluczowe pytanie brzmi: czy zakres zmniejsza się multiplikatywnie (log n), czy addytywnie (n)? Zobacz kod.
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) closelyPętla zagnieżdżona ze zmniejszającą się pętlą wewnętrzną: O(n log n)
Pętla zewnętrzna wykonywana n razy wraz z pętlą wewnętrzną O(log n) daje O(n log n) — taką strukturę ma sortowanie przez scalanie. Rozpoznanie wewnętrznego kroku O(log n) jest kluczowe podczas analizowania algorytmów sortowania.
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}')Zależne pętle wewnętrzne
Gdy zakres pętli wewnętrznej zależy od indeksu pętli zewnętrznej, należy liczyć łączną liczbę iteracji, a nie liczbę iteracji w każdym kroku. Pętla wewnętrzna wykonująca się od 0 do i daje sumę n(n-1)/2 = O(n^2). Zobacz kod.
# 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 = 384Analiza sortowania bąbelkowego krok po kroku
Sortowanie bąbelkowe wykonuje n(n-1)/2 porównań, więc ma złożoność O(n^2). Nawet przy wcześniejszym zakończeniu dane wejściowe posortowane odwrotnie nadal wymagają wszystkich porównań. To zbyt wolne dla dużych danych wejściowych.
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/2Pętle po napisach i podnapisach
Uwaga: operacja slicing w Pythonie ma złożoność O(k), więc nie jest bezpłatna, a konkatenacja napisów za pomocą + w pętli ma złożoność O(n^2), ponieważ za każdym razem kopiuje dane. Zamiast tego należy użyć ''.join(parts). Zobacz kod.
# 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'Wiele parametrów wejściowych
Przy dwóch danych wejściowych złożoność może uwzględniać oba parametry: O(m + n) dla oddzielnych operacji oraz O(m x n) dla operacji zagnieżdżonych. Dla grafów często stosuje się zapis O(V + E). Każdą zmienną należy nazywać jasno.
# 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)) # 50Pętle zagnieżdżone a wywołania sekwencyjne
Wywołanie funkcji nie jest bezpłatne — należy uwzględnić także jej wewnętrzną pętlę. Wywołanie pomocniczej funkcji O(n) n razy daje O(n^2). Podczas analizy zawsze należy zajrzeć do wnętrza wywołań traktowanych jak czarne skrzynki.
# 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]Praktyka: rozpoznawanie złożoności na pierwszy rzut oka
Warto wyrobić sobie nawyk: liczyć poziomy zagnieżdżenia pętli, sprawdzać, czy pętla wewnętrzna zależy od zewnętrznej, oraz zwracać uwagę na ukryte koszty wywołań funkcji i operacji slicing. Kod jest zagadką do samodzielnego rozwiązania.
# 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)Szybki test
Szybki test — sprawdźmy, jak dobrze zapamiętano metody analizy pętli. Warto zaufać własnemu rozumowaniu. 💪
Podsumowanie lekcji
Podsumowanie: pętle zagnieżdżone mnożą się, a niezależne sumują się; wewnętrzna pętla zmniejszająca zakres o połowę daje O(n log n), a ukryte koszty wywołań i operacji slicing również należy uwzględniać.
Często zadawane pytania
Czy lekcja „Analiza pętli i pętli zagnieżdżonych” jest bezpłatna?
Tak — pełny tekst „Analiza pętli i pętli zagnieżdżonych” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Analiza pętli i pętli zagnieżdżonych”?
Obliczą Państwo złożoność czasową pojedynczych pętli, pętli zagnieżdżonych oraz pętli ze zmniejszającymi się zakresami, takich jak wyszukiwanie binarne lub iteracje po trójkącie. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Analiza pętli i pętli zagnieżdżonych”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Notacja Big-O od podstaw
- Analiza pętli i pętli zagnieżdżonych
- Rekurencja i metoda drzewa rekurencji
- Złożoność pamięciowa i kompromisy