Сложность выполнения этого алгоритма?

Question

Учитывая a и b, меня попросят вычислить a^b с временем выполнения быстрее, чем O (b). Я придумал:

if(b == 1) return a; 
if(b % 2 == 0) 
    return findExp(a,b/2) * findExp(a,b/2); 
else 
    return findExp(a,(b/2)+1) * findExp(a,b/2); 

Мой вопрос, является сложность выполнения этого алгоритма логарифмическое время или полиномиальное время?

Answer 1

Ваш алгоритм O (b) не логарифмический.

В этой части кода return findExp(a,b/2) * findExp(a,b/2); вы вызываете ту же функцию, которая возвращает одно и то же значение два раза. В основном, вы тратите избыточное время на второй вызов.

Математически, если T (b) представляет время, требуемое для a^b в соответствии с вашим алгоритмом, оно равно T(b) = T(b/2) + T(b/2), где каждый член соответствует каждому вызову. T(b) = 2.T(b/2). Решите этот повтор, и вы получите T (b) в порядке b.

Чтобы сделать его логарифмическим, просто запретите этот избыточный вызов, сохранив значение в переменной.

Отредактированный код:

if(b == 1) return a; 
if(b % 2 == 0) 
    int x = findExp(a,b/2); 
    return x*x; 
else 
    int x = findExp(a,b/2); 
    return a*x*x; 

Теперь T(b) = T(b/2), так как вы вызываете findExp (а, Ь/2) только один раз (или в if частично или else части).

Это дает O(log(b)) алгоритма

Если вы хотите проверить это, запустить свой код и один упомянутый мною для некоторых большого б, скажем, Ь = 1000000000 и сопоставьте раз взял.

Answer 2

Это O (log (b)), поэтому он логарифмичен.