Ü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