Какова временная сложность функции, которая ниже рекурсивно

Question

int Do(int n) 
{ 
if(n<=2) 
    return 1; 
else 
return(Do(floor(sqrt(n))+n); 
} 

Можно ли принять рекурсивное отношение как T(square root(n)+n))+1? Если да, то как мне продолжить эту проблему?

Answer 1

Рекурсия не закончится (по крайней мере, теоретически, о чем вы, вероятно, говорите), когда это похоже на ваш вопрос. Причина: n + floor(sqrt(n)) больше, чем n.

Предполагаете, вы имеете в виду return Do(floor(sqrt(n))) + n. Я продолжаю общие соображения, чтобы ответить на этот вопрос, но будьте осторожны: есть некоторые пробелы, которые вы должны заполнить сами!

Я бы разделить вопрос о времени запуска на две части:

• Самое главное: Сколько рекурсии до базового варианта?
• Как совместить все рекурсии?

Количество рекурсии: Написать n как степень 2 (т.е. n=2^(ld n), где ld обозначает логарифм по основанию 2). Принимая квадратный корень от n соответственно. 2^(ld n) половинки экспонента. Чтобы достичь базового случая, мы должны вдвое уменьшить показатель, пока он не станет меньше единицы. Это приводит к вопросу: как часто мы должны вдвое сократить ld n, пока не достигнем чего-то <= 1. Ответ на этот вопрос примерно ld ld n. То есть у нас есть примерноld ld n рекурсии до основания.

Теперь мы делаем рекурсии и подвести итог:

T(n) = T(2^(ld 2)) 
    = T(2^((ld 2)/2)) + 1 
    = T(2^((ld 2)/4)) + 1 + 1 
    = ... 
    = T(2^((ld 2)/(2^(ld ld 2)))) + sum(1, i=0...(ld ld 2)-1) 
    = 1 + (ld ld 2) - 1 

Осталось упростить сумму и настроить детали для floor -части.

Answer 2

Возьмите любое число n и n = 2^k. Квадратный корень n означает половину показателя. Следовательно, могут быть только O (log k) квадратные корни.

n = 2^k поэтому k = log n. то O (log k) превращается в O (loglogn) ...