Solvequill Blog · coding · 3 dk okuma · 9 görüntülenme

İç içe iki döngü her zaman n² müdür?

İçteki döngü i'den başlıyorsa toplam çalışma sayısı

n^{2}

değil,

n^{2}

/2'dir. Sonuç yine

O (n^{2})

ama sebebi saymadan bilinmez.

Yayın tarihi: 25 Ağustos 2026

Ders yükleniyor…

Bu soruyu Solvequill'in anlattığı ders.

Soru

Aşağıdaki iç içe döngü toplam kaç kez çalışır? Sonucu n cinsinden kapalı biçimde yazınız ve karmaşıklığını belirtiniz.

Oran her satırda 1/2'ye yaklaşıyor — sabit çarpanın kendisi bu.

Önce neyi fark etmeli

İçteki döngünün sınırı sabit değil, dıştaki değişkene bağlı. Bu yüzden 'n çarpı n' demek yanlış olur; her i değeri için içteki döngünün kaç kez döndüğünü ayrı ayrı yazıp toplamak gerekir.

Adım adım çözüm

İncelenen kod:

Python

1toplam = 02for i in range(n):3 for j in range(i, n):4 toplam += 1

$i = 0$ için içteki döngü n kez, $i = 1$ için n-1 kez, $i = 2$ için n-2 kez döner. En sonda $i = n - 1$ için yalnızca 1 kez döner. Toplam:

T (n) = n + (n - 1) + (n - 2) + \dots + 1

Bu, ilk n doğal sayının toplamıdır ve kapalı biçimi bilinir:

T (n) = k = 1 \sum n k = \frac{n ( n + 1 )}{2}

$n = 100$ için sayıyla kontrol $e t : 100 \times \frac{101}{2} = 5050$ . İç içe iki tam döngü olsaydı 10 000 olurdu, yani yaklaşık yarısı:

T (100) = 5050 (tam \overset{c}{¸} ift d \overset{o}{¨} ng \overset{u}{¨} de 10 000)

Büyük n'de baskın terim $n^{2}$ /2'dir. Sabit çarpan -O'da düşer:

\frac{n ^{2} + n}{2} \sim \frac{n ^{2}}{2} \Rightarrow O (n^{2})

Cevap

T (n) = \frac{n ( n + 1 )}{2} = O (n^{2})

Karmaşıklık yine O( $n^{2}$ ) ama gerçek çalışma sayısı tam döngünün yarısı. -O sabit çarpanı gizler; pratikte iki kat fark eder ve ölçtüğünde bunu görürsün.

Bu soruda en sık yapılan hata

İzlemeyi mi tercih edersin? Yukarıdaki ders her satırı tek tek anlatıyor.

Kendi sorunu açıklamalı videoya dönüştür

Soruyu yaz veya fotoğrafını yükle; Solvequill çözümü adım adım anlatan bir video üretsin.

Solvequill'i aç