Algoritmaların Tasarımı ve Analizi #02 | İşlem Sayısı ve Büyüme

Eğitmen: Dr. Süleyman Burak ÇELİK

Geçen derste bir dizinin en büyük değerini bulduk. İlk değeri aday aldığımız için kalan her kutuda bir karşılaştırma yaptık. Altı kutuda beş karşılaştırma vardı. Bugün bu hesabı genelleştireceğiz: Veri büyüdüğünde işin nasıl büyüdüğünü, birkaç küçük algoritmayı gerçekten çalıştırarak göreceğiz. Doğrusal, karesel ve logaritmik davranış. Algoritmaların çalışma adımlarını gerçek konuşmayla eşleşen şemalar ve özgün örneklerle adım adım inceliyoruz. Bu derste: 1. Tek döngü: her kutuya bir ziyaret 2. İç içe döngü: tam kareyi doldur 3. Her farklı çifti yalnız bir kez say 4. Aynı boyut, farklı işlem sayıları 5. İki kat büyütme deneyi 6. Kesin sayıdan büyüme sınıfına 7. Daha iyi sınıf, her n’de daha az iş mi? 8. Her adımda kalan işi yarıya indir 9. Aynı uzunlukta farklı girdiler Bölümler: 0:00 Süreyi değil, yapılan işi sayalım 0:57 Bir işlem tam olarak ne demek? 1:54 Tek döngü: her kutuya bir ziyaret 2:46 İç içe döngü: tam kareyi doldur 3:37 Her farklı çifti yalnız bir kez say 4:32 Aynı boyut, farklı işlem sayıları 5:25 İki kat büyütme deneyi 6:23 Kesin sayıdan büyüme sınıfına 7:15 Daha iyi sınıf, her n’de daha az iş mi? 8:13 Her adımda kalan işi yarıya indir 9:08 Aynı uzunlukta farklı girdiler 10:06 Sıra sizde: n = 12 için sayın 11:00 Sayımın arkasındaki yapıyı görün Kaynak kitap: Jeff Erickson — Algorithms, 1. baskı (2019, CC BY 4.0), §0.6. Kavram ve konu sırası kaynak kitaptan izlenir; anlatım, şemalar ve sayısal örnekler özgündür. Ekrandaki sayılar açık varsayımlı öğretim modelleridir; gerçek cihaz ölçümü değildir. Kitap: https://jeffe.cs.illinois.edu/teaching/algorithms/ (yasal ve ücretsiz kaynak). Hedef kitle: bilgisayar mühendisliği ve yazılım öğrencileri.