Menganalisis Loop dan Loop Bersarang
Hitung kompleksitas waktu untuk loop tunggal, loop bersarang, dan loop dengan rentang yang menyusut seperti pencarian biner atau iterasi segitiga.
Menganalisis Loop dan Loop Bersarang adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Satu Perulangan: O(n)
Perulangan paling sederhana menjalankan badannya sebanyak n kali, sehingga kompleksitasnya O(n). Langkah yang lebih besar mengubah jumlah pengulangan, tetapi tidak mengubah kelasnya. Selalu mulai dengan menghitung berapa kali badan perulangan dijalankan. Lihat kodenya.
# 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)Perulangan Bersarang: O(n²) dan Lebih Besar
Dua perulangan yang bersarang, masing-masing sebanyak n kali, menghasilkan n x n = O(n^2); tiga perulangan menghasilkan O(n^3). Namun, jika perulangan bagian dalam berjalan dalam jumlah tetap, keseluruhannya tetap linear.
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)Perulangan Segitiga: O(n²/2) = O(n²)
Saat perulangan bagian dalam dimulai dari i+1, jumlah iterasinya membentuk segitiga: n(n-1)/2, yang tetap O(n^2) setelah faktor setengah dihilangkan. Masalah pasangan yang semuanya unik memiliki bentuk seperti ini.
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 droppedPerulangan dengan Rentang Menyusut: O(log n)
Saat variabel perulangan dibagi dua pada setiap langkah, kompleksitasnya menjadi O(log n). Pertanyaan kuncinya: apakah rentangnya menyusut secara perkalian (log n) atau secara penjumlahan (n)? Lihat kodenya.
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) closelyPerulangan Bersarang dengan Bagian Dalam yang Menyusut: O(n log n)
Perulangan bagian luar yang berjalan n kali dengan perulangan bagian dalam O(log n) menghasilkan O(n log n) — bentuk yang dimiliki pengurutan gabung. Menemukan langkah bagian dalam O(log n) adalah kunci untuk menganalisis algoritma pengurutan.
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}')Perulangan Bagian Dalam yang Bergantung
Saat rentang perulangan bagian dalam bergantung pada indeks bagian luar, hitung total iterasi, bukan jumlah per langkah. Perulangan bagian dalam yang berjalan dari 0 hingga i memiliki jumlah n(n-1)/2 = O(n^2). Lihat kodenya.
# 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 = 384Analisis Pengurutan Gelembung Langkah demi Langkah
Pengurutan gelembung melakukan perbandingan sebanyak n(n-1)/2 kali, sehingga kompleksitasnya O(n^2). Bahkan dengan penghentian lebih awal, input yang diurutkan terbalik tetap memerlukan setiap perbandingan. Algoritma ini terlalu lambat untuk input berukuran besar.
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/2Perulangan pada String dan Substring
Berhati-hatilah: pengirisan Python memiliki kompleksitas O(k), bukan tanpa biaya, dan penggabungan string dengan + di dalam perulangan memiliki kompleksitas O(n^2) karena string disalin setiap kali. Gunakan ''.join(parts) sebagai gantinya. Lihat kodenya.
# 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'Beberapa Parameter Input
Dengan dua input, kompleksitas mungkin menggunakan keduanya: O(m + n) untuk pekerjaan terpisah, dan O(m x n) untuk perulangan bersarang. Graf sering dinyatakan sebagai O(V + E). Beri nama setiap variabel dengan jelas.
# 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)) # 50Perulangan di Dalam Perulangan vs Pemanggilan Berurutan
Pemanggilan fungsi tidak gratis — perulangan di dalamnya juga harus dihitung. Panggil pembantu O(n) sebanyak n kali, maka hasilnya O(n^2). Saat menganalisis, selalu periksa isi pemanggilan yang tampak seperti kotak hitam.
# 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]Praktik: Mengenali Kompleksitas Sekilas
Bangun kebiasaan: hitung tingkat perulangan yang bersarang, periksa apakah perulangan bagian dalam bergantung pada bagian luar, dan waspadai biaya tersembunyi dalam pemanggilan fungsi serta pengirisan. Kode tersebut adalah teka-teki untuk dicoba.
# 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)Pemeriksaan Singkat
Pemeriksaan singkat — lihat seberapa baik trik analisis perulangan telah Anda pahami. Percayalah pada penalaran Anda kali ini. 💪
Rangkuman Pelajaran
Rangkuman: perulangan yang bersarang dikalikan dan perulangan independent dijumlahkan, perulangan bagian dalam yang membagi dua menghasilkan O(n log n), dan biaya tersembunyi di dalam pemanggilan serta pengirisan juga harus dihitung.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Menganalisis Loop dan Loop Bersarang” gratis?
Ya — teks lengkap “Menganalisis Loop dan Loop Bersarang” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Menganalisis Loop dan Loop Bersarang”?
Hitung kompleksitas waktu untuk loop tunggal, loop bersarang, dan loop dengan rentang yang menyusut seperti pencarian biner atau iterasi segitiga. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Menganalisis Loop dan Loop Bersarang” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Notasi Big-O dari Dasar
- Menganalisis Loop dan Loop Bersarang
- Rekursi dan Metode Pohon Rekursi
- Kompleksitas Ruang dan Pertukarannya