Какой более эффективный способ выполнения полномочий (с точки зрения временной сложности), с использованием рекурсии, с использованием цикла while или обоих?

Question

Я видел примеры кода алгоритмов «разделяй и властвуй» (или, по крайней мере, то, что я считаю «разделяй и властвуй») - одна общая группа примеров имеет тенденцию использовать рекурсию, в то время как другая использует в то время как контур. * * тысяча один

Вот пример рекурсии:

...
if (exponent%2==0) 
{ 
return Power(base*base, exponent/2); 
} 
else if (exponent%2==1)
{ 
    return base*Power(base*base, exponent/2); 
} 
...

И вот пример цикла while:

...
while (exponent>1)
{
    if (exponent%2 == 1)
        result *= base;
    exponent/=2;
    base *= base;
}
...

В обоих случаях действительно похоже, что они выполняются с одинаковым количеством операций. Число операций, выполняемых обоими подходами, ограничено функцией потолка T(exponent) = Θ(log_2(exponent)). Если мой анализ не верен, я не вижу, как один подход работает быстрее, чем другой. Я полагаю, что рекурсивный подход менее эффективен, чем циклический подход с точки зрения сложности пространства, потому что рекурсивный подход будет иметь пространственную сложность 2*(log_2(exponent)) (если этот анализ верен).

Является ли единственным преимуществом подхода while-loop то, что он требует меньше места?

Answer 1

Если предположить, что используемый вами компилятор нормальный, то да ... единственным преимуществом является меньший объем памяти.

Обратите внимание, что большинство компиляторов позволяют эффективно обрабатывать хвостовую рекурсию , который происходит, когда функция вызывает себя только как последний шаг выполнения (примеры приведены в статье).Как написано выше, ваш алгоритм рекурсии не является хвостовой рекурсией, потому что последний шаг перед возвратом - это умножение (base * Power), но это можно изменить, добавив переменную-накопитель в качестве аргумента, который умножается при каждом вызове, а затем возвращаяпоследний достигнутый вами аккумулятор.

Пример кода:

...
int Power(int base, int exponent, int accumulator)
{
    if (exponent%2==0) 
    { 
        return Power(base*base, exponent/2, accumulator); 
    } 
    else if (exponent%2==1)
    { 
        return Power(base*base, exponent/2, accumulator * base); 
    } 
}
...

, где Power всегда первоначально вызывается с помощью аккумулятора 1 (например, вы можете сделать альтернативную функцию power (a, b)), который просто вызывает Power (a, b, 1), если необходимо).

Answer 2

Версия с рекурсией хороша для дидактических целей, но версия loop быстрее.

Это не только из-за накладных расходов на вызовы, но и потому, что циклы могут быть развернуты компилятором, а зависимость от данных может распространяться легче.

Answer 3

это пример цикла цикла для расчета мощности базы: неправильно он будет вычислять базу ^ log (экспонента) вместо базы ^ экспонента

*метод «разделяй и властвуй» с использованием рекурсии даст сложность по времени: O (logn) * с использованием цикла n-1 произойдет операция умножения времени, поэтому TC: O (n)

если у вас есть мозг, вы можете решить, какойлучше по времени.

Answer 4

Понятие сложности времени, кажется, немного в вашем вопросе.

Если вы задумываетесь над вопросом «Как долго будет работать эта функция», то концепция временной сложности в действительности не имеет смысла. Вы, кажется, понимаете основы, поэтому знаете, что сложность 1000N + 100000 такая же, как и для N / 10000. Тем не менее, я также отмечу, что временные затраты для 1000N + 100000 намного больше, чем для N / 10000.

Понятие сложности относится к росту. Выражается скорость, с которой увеличивается потребление времени функцией с размером N (размер входных данных).

В мире затрат времени, циклический метод в большинстве случаев свергнет рекурсивный (я не думаю, что мне еще доводилось видеть случай, когда рекурсивное решение займет меньше времени даже при оптимизации компилятора ). Кроме того, как вы (и большинство авторов до меня) упомянули, требуемое пространство может быть больше (если не используется оптимизация хвостового вызова, оно должно быть заметно больше).

Если вам интересно, для чего нужна рекурсия (за пределами школы), то ответом будет простота кода (рекурсия может иногда создавать удивительно простой код при правильном использовании).

Answer 5

Для проблемы с полномочиями - да, циклы, вероятно, лучше благодаря возможности для оптимизации компилятора.Но вы должны понимать, что это не относится ко всем алгоритмам «разделяй и властвуй» (в случае, если вы на это намекаете в первом абзаце).

Кроме того, не забывайте, что некоторые разделяют иПарадигмы Conquer работают очень хорошо в распределенных системах.