ALGORİTMALAR VE PROGRAMLAMA - Deneme Sınavı - 10

ardışık arama algoritması için zaman karmaşıklığı O(n) dir.

Ikinci karşılaştırmada sağdaki üç eleman üzerinde işlem yapılır ve 5,6,7 olarak sıralanırlar.

Ikinci karşılaştırma adımında soldaki üç eleman üzerine işlem yapılır.

Aranan değer dizide mevcut ise 7 elemanlı dizi için 3 karşılaştırmada sonuca ulaşabilir.

I ve III dizileri sayılardan II dizisi ise String elemanlardan oluşuyor. Herhangi bir şekilde karşılaştırma yapılabilecek her dizi de ardışık arama yapılabilmektedir. Dolayısıyla her üç dizi için ardışık arama yapılabilir.

Dizi incelendiğinde hem 5 hem 10 bu dizi içinde yer almamakta. Dolayısıyla baştan sona tüm dizi elemanları kontrol edilmektedir. Dizi eleman sayısı 9 olduğundan 2*9 = 18 karşılaştırma yapılması gerekir.

Dizi incelendiğinde 2 dizinin ilk 65 ise dizinin 2. Toplamda 1 + 2 = 3 karşılaştırma yapmak gerekir.

Çok yüksek miktarda ardışık arama sonucu aranılan elemanlar bazen 1. Bazen 2., bazen 3. vb … bazen de 100. karşılaştırmada bulunacaktır. Sonuçta ortalamaya vurulduğu taktirde (1 + 999) / 2 = 50 sonucuna ulaşılmaktadır. Farklı şekilde olasılık olarak şöyle düşünelim. Toplamda 1000 arama yapılsa ve bu aramalar da 1000 ayrı sayı için olsa toplam ortalama arama sayısı (1+ 2+ 3+ … + 999) /1000 olacaktır. Sonuç  : (999 * 1000)/(1000*2) ~ 500 sayısı elde edilir.

Algoritma incelendiğinde aramanın dizinin son elemanından ilk elemanına doğru yapıldığı anlaşılır. -3 dizinin sondan 5. Elemanı ve 0 dizinin sondan 3. Elemanı olduğundan 5+3 = 8 karşılaştırma yapmak gerekir.

İkil arama yapılabilmesi için dizilerin sıralı olması gerekmektedir. Dikkatli incelendiğinde II dizisi alfabetik olarak sıralı bir dizidir. III dizisi de sıralı bir dizidir. Ancak I dizisi sıralı değildir. II ve III dizileri ikili arama için uygundur.

İkili arama yöntemi kullanıldığında iki elemanın da dizide olmadığı göz önünde bulundurarak her biri için 3 karşılaştırma yapması gerekir. Toplam 3+3 = 6 karşılaştırma yapmak gerekir.

İkili arama yapılırken 62 arayalım. Önce dizinin ortasındaki sayı yani 45 sayısı ile 62 sayısı karşılaştırılacaktır. 62 45’den büyük olduğu için dizinin sağ tarafındaki sayılar yani 54 58 62 87 100 sayılarının ortasındaki sayı bulunacak bu say 62 olunca arama bitirilecektir. Dolayısıyla 2 karşılaştırma yapılmış olacaktır. 45 sayısı da 1 karşılaştırmayla bulunacağından 1 + 2 = 3 karşılaştırmaya ihtiyaç vardır.

Çok yüksek miktarda ikili arama sonucu aranılan elemanlar bazen 1. Bazen 2., bazen 3. vb … bazen de 9. karşılaştırmada bulunacaktır. Sonuçta ortalamaya vurulduğu taktirde (1 + 9) / 2 = 5 sonucuna ulaşılmaktadır. İkili aramada en hızlı cevap 1. karşılaştırmada, en yavaş cevap da log2(512) = 9 karşılaştırmada elde edilecektir.

Sıralanmamış bir diziyi ikili arama yöntemiyle kullanmak ikili aramanın mantığına ters olacaktır. Sonuçta aranılan eleman dizi içerisinde olsa bile bulunmama ihtimali yüksektir. Soruda da her ne kadar gerek 31 gerek 3 dizi içerisinde yer alsa da bunlar algoritma tarafından bulunamayacaklardır. 31 aradığımızı düşünelim. Önce dizinin ortası 5 ile karşılaştırma yapılacak ve 5 in sağ tarafındaki dizi elemanları içerisinde 31 aranacak. İkinci kez 15 ile karşılaştırma yapılacak ve 15 in sağındaki elemanlarla bir defa daha karşılaştırma olacak ve sayı 3 ile karşılaştırılıp 3ün yanındaki sayı olan 23 ile bir defa daha karşılaştırma yapılacak. Sonuçta 4 karşılaştırmadan sonra elemanın dizide olmadığına karar verilecek. 3 için de aynı yöntemle 4 karşılaştırma neticesinde dizide olmadığına kanaat getirilecek. Sonuçta 4+4 = 8 karşılaştırma yapılmış olacak.

Bazı  algoritmaların  doğru  çalışması  için  dizilerin  sıralı  durumda  olması  gerektiği bilinmektedir. Sıralı durumda olmayan bir diziye bu türdeki bir arama algoritmasının uygulanması için dizinin öncelikle sıralı hale getirilmesi gerekir. Böyle bir durumda ise  sıralama  ve  arama  algoritmalarının  peş  peşe  çalışması  söz  konusu  olur.  Bu  sebeplerle  probleme uygun arama algoritmasının seçilmesi önemlidir.

ardisik_arama fonksiyonu kendisine gelen dizide, aranmak istenen sayıyı baştan sona doğru sırasıyla dizi elemanlarıyla karşılaştırmaktadır. Karşılaştırma sırasında aranan sayıya ulaştığında ise karşılaştırmadan çıkmaktadır. Bu doğrultudan hareketle;

ardisik_arama fonksiyonuna [7,12,1,6,15] dizisinde aranan1’in değeri olan 12 gönderildiğinde iki karşılaştırma işlemi yapmış olacaktır. aranan2’nin değeri olan 15 gönderildiğinde ise beş karşılaştırma işlemi yapmış olacaktır. Dolayısıyla toplamda yedi işlem gerçekleşmiş olacaktır.

ardisik_arama fonksiyonu kendisine gelen dizide, aranmak istenen sayıyı baştan sona doğru sırasıyla dizi elemanlarıyla karşılaştırmaktadır. Karşılaştırma sırasında aranan sayıya ulaştığında ise karşılaştırmadan çıkmaktadır. Bu doğrultudan hareketle;

ardisik_arama fonksiyonuna [7,12,1,12,15] dizisinde aranan1’in değeri olan 12 gönderildiğinde, ilk karşısına çıkan 12’den sonra karşılaştırma işlemini sonlandıracaktır. Dolayısıyla iki karşılaştırma işlemi yapmış olacaktır. Ancak aranan2’nin değeri de 12 olduğu için yine aynı şekilde sadece iki karşılaştırma işlemi yapmış olacaktır. Dolayısıyla toplamda dört karşılaştırma işlemi gerçekleşmiş olacaktır.

ardisik_arama fonksiyonu kendisine gelen dizide, aranmak istenen sayıyı baştan sona doğru sırasıyla dizi elemanlarıyla karşılaştırmaktadır. Karşılaştırma sırasında aranan sayıya ulaştığında ise karşılaştırmadan çıkmaktadır. Bu doğrultudan hareketle;

ardisik_arama fonksiyonuna [7,12,1,12,15] dizisinde aranan1’in değeri olan 12 gönderildiğinde, ilk karşısına çıkan 12’den sonra karşılaştırma işlemini sonlandıracaktır. Dolayısıyla iki karşılaştırma işlemi yapmış olacaktır. Ancak aranan2’nin değeri de 12 olduğu için yine aynı şekilde sadece iki karşılaştırma işlemi yapmış olacaktır. Dolayısıyla toplamda dört karşılaştırma işlemi gerçekleşmiş olacaktır.