Анализ выполнения короткого алгоритма

Question

я получил следующий код Дано:

public class alg 
{ 
    public static int hmm (int x) 
    { 
     if (x == 1) 
     { 
      return 2; 
     } 
     return 2*x + hmm(x-1); 
    } 

    public static void main (String[] args) 
    { 
     int x = Integer.parseInt(args[0]); 
     System.out.println(hmm(x)); 
    } 
} 

Так первый вопрос, что же рассчитывать этот алгоритм? Я только что набрал и запустил его в eclipse , поэтому я могу лучше видеть, что он делает (раньше он был псевдокодом, я не мог ввести его здесь, поэтому я набрал код). Я понял, что этот алгоритм делает следующее: он будет принимать входные данные и умножать их на следующий номер. Итак, как примеры:

input = 3, output = 12 because 3*4 = 12. 
Or Input = 6, output 42 because 6*7 = 42. 

Alright, следующий вопрос, моя проблема. Мне предлагается проанализировать время выполнения этого алгоритма, но я не знаю, с чего начать. Я бы сказал, что в начале, когда мы определяем x, у нас уже есть time = 1 Цикл if дает time = 1 тоже, я считаю. Последняя часть, return 2x + alg(x-1) должна давать «что-то^x» или ..? Таким образом, в конце концов, мы получили что-то вроде "что-то^х" + 2, я сомневаюсь Вот так:/

редактировать, удалось набрать псевдокод тоже :)

Input: Integer x with x > 1 
if x = 1 then 
    return 2; 
end if 
return 2x + hmm(x-1); 

Answer 1

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

Что это значит?

Давайте hmm(3) как пример:

1. 3 != 1, поэтому мы рассчитываем 2 * 3 + hmm(3-1). Вниз уровень рекурсии.
2. 2 != 1, поэтому мы рассчитываем 2 * 2 + hmm(2-1). Вниз уровень рекурсии.
3. 1 == 1, поэтому возвращаем 2. Больше нет рекурсий, таким образом hmm(2-1) == hmm(1) == 2.
4. Резервное копирование на один уровень рекурсии, получаем 2 * 2 + hmm(1) = 2 * 2 + 2 = 4 + 2 = 6. Таким образом hmm(2) = 6
5. Другой уровень резервного копирования, мы получим 2 * 3 + hmm(2) = 6 + 6 = 12

Если присмотреться, то алгоритм вычисляет:

2*x + ... + 4 + 2

Мы можем изменить это и фактор из 2 и получить

2 * (1 + 2 + ... + x).

Который является arithmetic progression, для которых у нас есть хорошо известная формула (а именно x² + x)

Сколько времени это займет?

Асимптотическое время работы O(n).

Нет циклов, поэтому нам нужно только подсчитать количество рекурсий. Можно было бы искусить подсчет отдельных этапов расчета, но они постоянны с каждым шагом, поэтому мы обычно объединяем их в постоянный коэффициент k.

Что означает O(n)?

Ну ... мы делаем x - 1 шагов рекурсии, уменьшая x по 1 на каждом шаге, пока мы не достигнем x == 1. От x = n до x = 1 есть n - 1 таких шагов. Таким образом, нам нужны операции k * (n - 1).

Если вы думаете, что n быть очень большим, - 1 становится пренебрежимо малым, поэтому мы его бросаем. Мы также понижаем постоянный коэффициент, потому что для больших n, O(nk) и O(n) тоже не так уж и отличаются.

Answer 2

Функция вычисляет

f(x) = 2(x + x-1 + x-2 + ... + 1) 

будет работать в O(x), т. Е. На постоянное время вызывается x раз O(1).