Bir Sayının Üssünü O(logn) Zamanda Hesaplamak

Posted On April 2, 2019

Bir x sayısının n’inci üssünü almak için akla gelen ilk yöntem x sayısını n – 1 kere kendisi ile çarpmaktır.

int power(int x, int n){
    if(n == 0) return 1;
    int ans = x;
    for(int i = 0; i < n-1; ++i)
        ans *= x;
    return ans;
}

Kolaylıkla görülebileceği üzere bu algoritmanın zaman karmaşıklığı n ile lineer olarak değişmektedir. Neyseki biz zaman karmaşıklığını logaritmik olacak şekilde düşürebiliriz.

Kolayca anlaşılması adına n = 13 ve herhangi bir x için algoritmamızı inceleyelim. Öncelikle 13’ü 2 tabanında yazarak başlayalım. 13 sayısı 2 tabanında şeklinde yazılır. Yani bizim hesaplamamız gereken değer ‘ye eşittir. Kolayca görebiliriz ki bu değeri şu şekilde yazabiliriz.

Herhang bir üs alma işlemini bu şekle getirdiğimizde bize gerekebilecek değerler dizisinin elemanlarıdır.

Buradan kolayca görebiliriz ki eğer yine logaritmik zaman karmaşıklığında bu elemanları hesaplayabilirsek tüm işlemi logaritmik zaman karmaşıklığında yapabiliriz.

Bu değerleri hesaplamanın kolay bir yolu ‘i sürekli kendi ile çarpmaktır. Bu şekilde her adımda bir ifadeyi elde ettiğimiz ve en fazla ifade olacağından zaman karmaşıklığımız logaritmik olacaktır.

Peki dizinin bu elemanlarından hangilerini çarpmalıyız ki sonucu elde edelim? Burada ‘in oluşturduğu seride her bir elemanı hesaplarken n’de bu elemana karşılık gelen basamağın 1 ya da 0 olmasına bakarız. Eğer 1 ise cevabı şu anki ile çarparız.

Özetlemek gerekirse adım adım:

1 – Şu an ki basamağın değerini öğrenmek için n’in 2’den kalanını bul.

2 – Eğer 1 ise cevabı ‘in şu anki değeri ile çarp.

3 – Basamağı Kaydırmak için ‘i 2 ile kalansız böl, ‘i kendi ile çarparak güncelle.

4 – Eğer 0’a eşit ise işlemi bitir değilse 1’e dön

Burada basamak sayısı tanedir ve biz de tam olarak bu kadar işlem yapacağımız için zaman karmaşıklığımız O(logn)’dir.

için algoritmamızı gösterelim:

olarak tanımlayalım.

1.Adım: , 2’den kalanı 1 bu yüzden cevap değişkenini ile çarparak güncelleyelim ardından ‘i güncelleyelim,n’i de iki ile kalansız bölerek yeni basamağa getirelim :

2.Adım : , 2’den kalanı 0 bu yüzden sadece ve n’i güncelliyoruz.

3.Adım:

4. Adım: , 2’den kalanı 1

n = 0 olduğundan işlemi bitiriyoruz ve cevabımızı 1.594.323 olarak buluyoruz.

Artık mantığı oturttuğumuza göre koda dökebiliriz. Aşağıda örnek bir C/C++ kodu vardır.

int power(int x, int n){
    int cevap = 1;
    while(n != 0){
        if(n % 2 == 1){ //Eğer şu anki bit açık ise  
            cevap = cevap * x; // Cevabı x ile çarparak güncelle
        }
        x *= x; // x'in değerini yükselt
        n /= 2; // biti kaydır.
    }
    return cevap;
}