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

Ardışık arama algoritmasının gerçeklenmesi sırasında, n  elemanlı  bir  dizi  için  en  fazla  n  adet  karşılaştırma  yapılması  gerekmektedir.  Dolayısıyla ardışık aramanın en kötü durumdaki zaman karmaşıklığının O(n) olduğunu söyleyebiliriz. İkili arama algoritması ise n elemanlı bir dizi için en kötü durumda log₂(n) adet karşılaştırma yapmaya ihtiyaç duymaktadır. Dolayısıyla ikili arama algoritmasının en kötü durumdaki zaman karmaşıklığının O(log(n)) olduğunu söyleyebiliriz. Bu karşılaştırmadan görüleceği üzere, ikili arama algoritması ardışık aramaya kıyasla çok daha hızlı çalışan bir algoritmadır. Örnek olarak, 16 elemanlı bir dizinin içerisinde arama yapılacağını ve aranan elemanın bu dizide yer almadığını varsayalım. Bu durumda, ardışık arama 16 adet karşılaştırma işlemi yaptıktan sonra sonuca ulaşacaktır. Buna karşın, ikili arama algoritması 4 adet karşılaştırma işlemi yaparak sonuca ulaşabilir. Böyle küçük bir dizi üzerinde bile, yapılacak karşılaştırma işlem sayıları arasında büyük bir fark olduğu görülmektedir. Dolayısıyla, içerisinde arama yapılacak olan dizi sıralı ise, işlem hızı açısından değerlendirildiğinde ikili arama algoritması tercih edilmelidir.

Ardışık arama algoritmasının gerçeklenmesi sırasında, n  elemanlı  bir  dizi  için  en  fazla  n  adet  karşılaştırma  yapılması  gerekmektedir.  Dolayısıyla ardışık aramanın en kötü durumdaki zaman karmaşıklığının O(n) olduğunu söyleyebiliriz. İkili arama algoritması ise n elemanlı bir dizi için en kötü durumda log₂(n) adet karşılaştırma yapmaya ihtiyaç duymaktadır. Dolayısıyla ikili arama algoritmasının en kötü durumdaki zaman karmaşıklığının O(log(n)) olduğunu söyleyebiliriz. Bu karşılaştırmadan görüleceği üzere, ikili arama algoritması ardışık aramaya kıyasla çok daha hızlı çalışan bir algoritmadır. Örnek olarak, 16 elemanlı bir dizinin içerisinde arama yapılacağını ve aranan elemanın bu dizide yer almadığını varsayalım. Bu durumda, ardışık arama 16 adet karşılaştırma işlemi yaptıktan sonra sonuca ulaşacaktır. Buna karşın, ikili arama algoritması 4 adet karşılaştırma işlemi yaparak sonuca ulaşabilir. Böyle küçük bir dizi üzerinde bile, yapılacak karşılaştırma işlem sayıları arasında büyük bir fark olduğu görülmektedir. Dolayısıyla, içerisinde arama yapılacak olan dizi sıralı ise, işlem hızı açısından değerlendirildiğinde ikili arama algoritması tercih edilmelidir.

Ardışık arama ve ikili arama algo­ritmaları

dizinin sıralı durumda olması

Ardışık arama

I, II ve III

İkili arama

Özyinelemeli fonksiyon

Return

Zaman karmaşıklığı

O(n)

O(log(n))

Doğru yanıt E seçeneğidir.

Doğru yanıt D sseçeneğidir.

Doğru yanıt A seçeneğidir.

Doğru cevap A seçeneğidir.