ALGORİTMA TASARIMI VE ANALİZİ
ARAŞTIRMA SORULARI-2
1. Aşağıdaki fonksiyonları asimptotik büyüme hızlarına göre küçükten büyüğe doğru sıralayınız:
(n  2)!,5log(n  100)10 ,22n ,0.1n4  2n3  5,ln 2 n, 3 n,3n
2.
Aşağıdaki algoritma verilsin:
Secret (A[0,1,2,…,n-1])
// girdi: n reel sayıdan oluşan A[0,1,2,…,n-1] dizisi.
minval  A[0]; maxval  A[0]
for i = 1 to n-1 do
if A[i] < minval
minval  A[i]
if A[i] > maxval
maxval  A[i]
return maxval – minval
Yukarıda verilen Secret algoritmasına göre aşağıdaki soruları cevaplayınız:
a. Girdi olarak alınan n elemanlı dizide sayıların büyükten küçüğe doğru sıralandığını kabul
edersek, bu algoritmanın zaman karmaşıklığı ne olur? Yani, bütün temel işlemleri tespit edip
her birinin kabul ettiğimiz duruma göre kaç kez tekrarlandığını bulunuz. Buradan hareketle de
algoritmanın karşılık geldiği karmaşıklık sınıfını bulunuz. Bu zaman karmaşıklığını hem toplam
adım sayısı olarak hem de asimptotik olarak ifade ediniz.
b. Girdi olarak alınan n elemanlı dizide sayıların küçükten büyüğe doğru sıralandığını kabul
edersek, bu algoritmanın zaman karmaşıklığı ne olur? Yani, bütün temel işlemleri tespit edip
her birinin kabul ettiğimiz duruma göre kaç kez tekrarlandığını bulunuz. Buradan hareketle de
algoritmanın karşılık geldiği karmaşıklık sınıfını bulunuz. Bu zaman karmaşıklığını hem toplam
adım sayısı olarak hem de asimptotik olarak ifade ediniz.
c. Girdi olarak alınan n elemanlı dizide sayıların hepsinin eşit olduğunu kabul edersek, bu
algoritmanın zaman karmaşıklığı ne olur? Yani, bütün temel işlemleri tespit edip her birinin
kabul ettiğimiz duruma göre kaç kez tekrarlandığını bulunuz. Buradan hareketle de
algoritmanın karşılık geldiği karmaşıklık sınıfını bulunuz. Bu zaman karmaşıklığını hem toplam
adım sayısı olarak hem de asimptotik olarak ifade ediniz.
d. Özel olarak girdi olarak 7 elemanlı [1,3,7,8,6,4,2] dizisini alırsak zaman karmaşıklığı ne olur?
Bu zaman karmaşıklığını hem toplam adım sayısı olarak hem de asimptotik olarak ifade
ediniz.
3.
2. Soruda verilen Secret algoritması aşağıdaki gibi değiştirilsin:
Secret (A[0,1,2,…,n-1])
// girdi: n reel sayıdan oluşan A[0,1,2,…,n-1] dizisi.
minval  A[0]; maxval  A[0]
for i = 1 to n-1 do
if A[i] < minval
minval  A[i]
if A[i] > maxval
maxval  A[i]
else
minval  A[i]; maxval  A[i]
return maxval – minval
Buna göre, sizce bu şekilde tanımlanan algoritma minval ve maxval değerlerini doğru olarak
hesaplamakta mıdır? Değilse, neden? [1,3,5,7,9,11] girdi olarak alınırsa bu algoritma hangi
sonucu üretir? [1,3,3,4,4,7,6] dizisi girdi olarak alınırsa bu algoritma hangi sonucu üretir? İki
girdi içinde sonucu üretene kadar yürütülen toplam adım sayısını bulunuz.
Download

Araştırma Soruları-2