как рассчитать временную сложность этого кода? и что это будет?

Question

Какова будет временная сложность? Это код, который сложности необходимо найти: Я не могу понять рекурсию часть, главным образом:/

void xyz(int n) 
{ 
    for (int i=0;i<n;i++) 
     do something; 
    if (n) 
     for (int i=0;i<n;i++) 
     xyz(n-1); 
    else return; 
} 

Answer 1

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

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

Если временная сложность возрастает с той же скоростью, что и размер входного файла, он линейный или класс сложности O (n). Если сложность возрастает экспоненциально по сравнению с размером ввода, она может быть, например, в классе O (n^2).

Рекурсия определенно может оказаться сложной, но идея состоит в том, чтобы «расширить ее», в частности, путем установления отношения повторения. Вот действительно хороший учебник по использованию рекурсивных отношений, чтобы найти временную сложность рекурсивных алгоритмов: http://www.cs.duke.edu/~ola/ap/recurrence.html