время работы changetoBinary алгоритма?

Question

Я разработал алгоритм преобразования степеней 10 в двоичный, предполагая, что n является степенью 2. Я использовал метод Гаусса, чтобы использовать быстрое время выполнения этого хорошего метода. Для этого я делю п над 2 и отправить его методу Gauess следующим образом:

changetoBinary(n) 
if n=1 
    return binary of 10 which is 1010 

else 

return gauess(n/2,n/2) 

Очевидно, что метод Guess будет первым разделить, а затем победить и затем объединить. В конце мы изменили номер на двоичный. Теперь я задаюсь вопросом о времени работы алгоритма: я понимаю, что поскольку время выполнения Guess - это Theta (n^log3 (base2)), мы можем сказать, что время работы этого алгоритма также одинаково, поскольку большая часть работы выполнена Guess.On с другой стороны, когда я пытаюсь найти рекуррентное отношение, я прихожу с T (n/2) + O (n), который является Theta (n), поэтому какой из них правильный? Я пропустил sth в своем вычислении, Я получаю противоречие?

Answer 1

Рекуррентное отношение вашего алгоритма не равно T (n) = T (n/2) + n;

сложность вашего алгоритма - O (1). , так что вы правы, что сложность функции gauess будет сложностью вашего алгоритма.

, если ваш алгоритм был бы: change_to_binary (п) { change_to_binary (п/2);} .....

то Т (п) = Т (п/2) было бы вашим рекоммендовать. связь.