ünite 6 · Problem Çözme
·
ders 6.3
Adım saymak: algoritma ne kadar hızlı?
Doğrusal, karesel, logaritmik: girdi büyüyünce adım sayısı nasıl büyür?
9 dk
22 / 22
tamamlandı
İki algoritma aynı işi yapıyorsa hangisi "daha iyi"? Saniye ölçmek bilgisayara bağlı; onun yerine adım sayarız ve girdi büyüdükçe adımın nasıl büyüdüğüne bakarız.
| Büyüme | Örnek | n = 1000 için adım |
|---|---|---|
| sabit | dizinin ilk elemanını al | 1 |
| logaritmik (log n) | ikili arama | ~10 |
| doğrusal (n) | doğrusal arama, toplam | 1.000 |
| karesel (n²) | kabarcık sıralama, iç içe döngü | 1.000.000 |
Sezgi
- Tek döngü → doğrusal.
- İç içe iki döngü (ikisi de n) → karesel.
- Her adımda problemi yarılayan → logaritmik.
1000 elemanda fark hissedilmez; bir milyonda karesel algoritma bir trilyon adım — dakikalar, saatler. Bu yüzden sıralı veri + ikili arama, sırasız veri + doğrusal aramayı ezer.
Önce doğru çalışan bir çözüm yaz; sonra adımlarını say; sonra gerekiyorsa hızlandır. Erken hızlandırma, okunmaz kod üretir.
akış şeması
elips: başla/bitir · dikdörtgen: işlem · paralelkenar: girdi/çıktı · baklava: karar
flowchart LR
A[Girdi n] --> B{Kaç döngü?}
B -- yok --> C[sabit]
B -- bir --> D[doğrusal n]
B -- iç içe iki --> E[karesel n²]
B -- her adım yarılıyor --> F[logaritmik log n]
sözde kod
adımlar
1doğrusal: her eleman için 1 iş → n adım2karesel: her eleman için her eleman → n × n adım3logaritmik: her adımda yarısını at → log n adım
aynısı C# ile
C#
1int[] d = new int[1000];2int adim = 0;3// doğrusal4for (int i = 0; i < d.Length; i++) adim++;5Console.WriteLine("tek döngü: " + adim);6// karesel7adim = 0;8for (int i = 0; i < d.Length; i++)9 for (int j = 0; j < d.Length; j++) adim++;10Console.WriteLine("iç içe: " + adim);
senin sıran
Bir dizide tekrar eden eleman var mı? İki çözüm yaz: (1) iç içe döngüyle her çifti karşılaştır, (2) önce sırala, sonra komşuları karşılaştır. n = 10.000 için ikisinin adım sayısını tahmin et.
kendini sına Girdi 10 kat büyüyünce karesel algoritmanın adım sayısı kaç kat büyür?
100 kat (10²). Doğrusal 10 kat, logaritmik yalnızca birkaç adım artar.
tamamlandı
İşaret bu tarayıcıda kalır. XP için
giriş yap — her ders +15 XP.