Üs alma işlemi kullanılan programlama dilinin standart olarak verdiği işlemler ile gayet kolay olarak yapılabilen bir işlemdir.En basit hali ile çözüm şu şekildedir.
def brute(num, x):
result = 1
for i in range(x):
result *= num
return result
Bu çözüm iteratif olarak yazılmış ve O(n) karmaşıklığına sahip hoş olmayan bir çözümdür. Şimdi bu çözümü Divide and Conquer mantığına uygun bir çözüm ile yazalım.
def div_conq(num, x):
if x == 0:
return 1
elif x % 2 == 0:
return div_conq(num, x / 2) * div_conq(num, x / 2)
else
return num * div_conq(num, x / 2) * div_conq(num, x / 2)
Çözümü divide and conquer mantığına göre çözsekte karmaşıklıkta hala değişiklik olmadı ve zaman karmaşıklığımız O(n). Biraz dikkat ederseniz gereksiz tekrarlar olduğunu fark edebilirsiniz. Bunları önlemek için aşağıdaki gibi bir yol izleyebiliriz.
def div_conq(num, x):
if x == 0:
return 1
temp = div_conq(num, x / 2)
if x % 2 == 0:
return temp * temp
else:
return num * temp * temp
Artık karmaşıklığımız O(logn) olmuştur. Fakat yazdığımız kod negatif sayısal için çalışmayacaktır. Ufak bir ekleme ile şu hale getirebilriz.
def div_conq(num, x):
if x == 0:
return 1
temp = div_conq(num, x / 2)
if x % 2 == 0:
return temp * temp
else:
if(x > 0):
return num*temp*temp;
else:
return (temp*temp)/num;
Comments
comments powered by Disqus