большая O - рекурсия вместо умножения

Работа над методом замены умножения.большая O - рекурсия вместо умножения

public static int mult(int num, int repeat){ 
     if (repeat == 0) return 0; 
     if (repeat == 1) return num; 
     return num + mult(num, repeat - 1); 
    }

С точки зрения времени и пространства сложности, это было бы O (к) время, когда к является повтор и О (1) пространство?

источник

2017-01-22 Bao Thai

* «Работа над методом замены умножения» * - почему? – jonrsharpe

Опрос вопросов, а не замена оператора. Просто работаю над своими навыками рекурсии. @jonrsharpe –

@ Снова приносите свои извинения, как я могу это переместить? Я просто видел много вопросов о Большом o здесь, поэтому я думал, что это разрешено. –

Это O (K) время, как вы будете называть эту функцию один раз за repeat, и каждый вызов O (1). Тем не менее, это также O (k) пространство a, у вас будет k кадров стека, прежде чем вы нажмете условие завершения (в отсутствие оптимизации рекурсии хвостового вызова).

источник

2017-01-22 22:50:46

Исправьте меня, если я ошибаюсь, но хвостовая рекурсия не может применяться здесь, так как 'num' должен храниться до тех пор, пока возврат из рекурсивного вызова, поэтому стоп-фрейм с 'num' не может быть отброшен. – Arkadiy

Вот версия, совместимая с хвостом рекурсии: http://stackoverflow.com/questions/1149150/tail-recursive-method-to-multiple-2-numbers – Arkadiy

@Arkadiy Хороший оптимизатор, вероятно, может сказать, что 'num' не будет вообще не изменилось, поэтому я думаю, что рекурсия хвоста может применяться. Я не знаю, умны ли они. Если бы это было что-то вроде 'num + mult (num-1, repeat-1)', это изменило бы вещи [хотя, конечно, это больше не было бы умножением]. – ajb

большая O - рекурсия вместо умножения

ответ

Смежные вопросы