Recursive (Özyinelemeli) Fonksiyonlarda Zaman Denklemini Bulma

Recursive (özyinelemeli) algoritmaların analizini gerçekleştirme yöntemleri olan iteration, substition, master ve recurrence yöntemlerini kullanabilmek için öncellikle fonksiyonun zaman denkleminin T(n) cinsinden elde edilmesi gerekmektedir.

Oldukça basit bir işlem olmakla birlikte ana gereksinim analiz edilmek istenen algoritmanın çalışma mantığının kavranmasıdır. Bu makalede Binary Search algoritmasının öz yinelemeli fonksiyonu üzerinden örnekler ile T(n) denklemini elde edeceğiz.

İzlenecek Yol

Örneklere geçmeden önce teorik olarak izleyeceğimiz adımlardan bahsetmek gerekirse fonksiyonumuzu satır satır okuyacağız ve çalışma mantığını anlayacağız. Daha sonra sabitler, döngüler ve kendini çağırmalar için denklem değişkenlerini yerine koyacağız.

Binary Search Algoritmasının Zaman Denklemini Elde Etme

Binary search algoritması bilindiği üzere sıralı elemanlardan oluşan sayı kümesinde bir arama işlemi gerçekleştirir. Önce kümenin tam ortasındaki elemana bakar ve aranan eleman o ise geri döndürülür. Aranan eleman ortadaki elemandan büyükse kümenin ortasından sonuna kadar olan kısmında aynı işlem tekrarlanır. Aranan eleman küçük ise de kümenin başlangıcından ortadaki elemana kadar olan kısım alınarak tekrarlanır.

Algoritmayı anladıktan sonra koda geçecek olursak ilk önce bir if kontrolü yapılıyor. Bu sabite O(1) diyebiliriz. Bu if içerisinde ise bir değişken ataması yapılarak başka bir if kontrolü yapılmış. Bu iki satır da sabit oldukları için kendilerine O(1) diyebiliriz.

Sabit kısımların ardından asıl önemli kısım olan recursive kısım gelmektedir. if (arr[mid] > x) kontrolünün şartı sağlanırsa yani dizinin ortasındaki eleman aranan sayıdan büyükse fonksiyon kendisini çağırıyor ve parametre olarak dizinin ilk elemanından orta elemanına kadar olan kısım veriliyor. Yani artık eleman sayısı yarıya inmiş durumda.

Bu if şartı sağlanmıyor ise dizinin ortasındaki eleman aranan sayıdan küçük veya eşit demektir. Böylelikle kümenin ortasından sonuna kadar olan kısım parametre olarak verilerek aynı işlemler tekrarlanıyor.

İki recursive çağırım da şarta bağlı olduğundan aslında yalnızca bir kez recursive çağırım yapılıyor. Ayrıca iki çağırımda da eleman sayısı yarıya iniyor. Dolayı koddaki işaretlenmiş recursive kısmına T(n/2) diyebiliriz.

En sonda ise elemanın bulunmama durumunda -1 sayısı döndürülüyor. Buna da O(1) diyebiliriz.

Bu adımların ardından zaman denklemimizi aslında yazdık. Toparlayacak olursak toplamda 4 kez O(1) sonucuna ve 1 kere T(n/2) sonucuna ulaştık. Buna göre T(n) denklemimiz:

T(n) = T(n/2) + 4O(1)

Elde ederiz. O(1)’ler sabit olduğu için direkt c dersek denklemin son hali:

T(n) = T(n/2) + c

Elde etmiş oluruz.

Sonuç

Bu yazıda Binary Search algoritmasının recurisve fonksiyonu için zaman fonksiyonunu yazdık. Özet olarak algoritmanın çalışma prensibini tespit ettikten sonra recursive çağırımların kaç kez çalıştığını saptamak denklemi yazmanın büyük bir kısmını oluşturmaktadır. Sabitler de eklenerek denklem kolayca elde edilmektedir.

Sonraki yazılarda bu elde ettiğimiz denklemi çeşitli yöntemler kullanarak çözerek algoritma analizini gerçekleştireceğiz.