Сложность времени и пространства рекурсивного и нерекурсивного малого алгоритма

Question

Рассмотрим две функции, которые принимают в качестве параметра целое число без знака и возвращают количество цифр этого числа. Одна функция рекурсивна, а другая нерекурсивна.

С точки зрения сложности, какая реализация лучше?

Используемый язык - C/C++.

Здесь не-рекурсивная функция:

int nbOfDigitsNR(int nb) { 
int i=0 
while(nb!=0){ 
nb=nb/10; 
++i; 
} 
return i; // i is the number of digits 
} 

рекурсивная функция:

int nbOfDigitsNR(int nb) { 
static int i; 
if (nb!=0){ 
i=i+1; 
nbOfDigitsNR(nb/10);} 
return i; 
} 

Я полагаю, что временная сложность такой же: О (п), и сложность пространства другое: O (n) рекурсивное. O (1) нерекурсивный.

Answer 1

Говоря о том, что функция рекурсивна или нерекурсивна, не сообщает нам что-то о ее сложности.

Он может быть равен или один из них с меньшей сложностью .. он полностью зависит от алгоритма.

У меня есть синий и серый автомобиль. Какой из них быстрее?

Answer 2

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

Разница заключается в сложности пространства и как язык программирования в вашем случае C++ обрабатывает рекурсию.

Ваш пример иллюстрирует именно это. Обе функции будут иметь одинаковую сложность по времени, тогда как рекурсивная будет иметь большую сложность пространства, поскольку C++ выделяет переменные для каждого рекурсивного вызова в стеке.

Вы в праве в том, что касается времени и пространства, если n представляет собой число цифр. Если n представляет целое число, замените его на lg (n).