Порядок роста конкретной рекурсивной функции - PullRequest
Новая
       18

Порядок роста конкретной рекурсивной функции

3 голосов
/ 01 марта 2012

Каков порядок роста следующей функции? 

    static int counter = 0;

    static void Example(int n)
    {
        if (n == 1) return;

        for (int i = 0; i < n; i++)
        {
            counter++;
        }

        Example(n / 2);
    }

Чтобы решить ее, я сделал следующее:

Сначала я избавился от внутреннего цикла for вЧтобы получить в итоге: 

    static void Example(int n)
    {
        if (n == 1) return;            

        counter++;

        Example(n / 2);
    }

Анализируя это, я смог сказать, что порядок роста этого метода был log base 2 из n.

, поэтому я думаю,Окончательный ответ будет лог база 2 раза что-то еще.Как я могу это выяснить?

Ответы [ 2 ]

6 голосов
/ 01 марта 2012

Давайте рассмотрим как оригинальную, так и модифицированную функцию.В исходной функции у вас есть следующий объем работы:

  • Постоянный объем работы для проверки базового случая.
  • O (n) работа для подсчета числа.
  • Работа, необходимая для рекурсивного вызова чего-то наполовину меньше.

Мы можем выразить это как отношение повторения:

  • T (1) = 1
  • T (n) = n + T (n / 2)

Посмотрим, как это выглядит.Мы можем начать расширять это, заметив, что

T (n) = n + T (n / 2)

= n + (n / 2 + T (n / 4))

= n + n / 2 + T (n / 4)

= n + n / 2 + (n / 4 + T (n / 8))

= n + n / 2 + n / 4 + T (n / 8)

Мы можем начать видеть образец здесь. Если мы расширим бит T (n / 2) k раз, мы получаем

T (n) = n + n / 2 + n / 4 + ... + n / 2 k + T (n / 2 k )

В конце концов, это останавливается, когда n / 2 k = 1. Когда это происходит, мы имеем

T (n) = n + n / 2 + n / 4 + n / 8 + ... + 1

Что это оценивает? Интересно, что эта сумма равна 2n + 1, потому что суммаn + n / 2 + n / 4 + n / 8 + ... = 2n. Следовательно, этой первой функцией является O (n). Мы могли бы также прийти к этому выводу, используя основную теорему , но интересно также увидеть этот подход.

Так что теперь давайте посмотрим на новую функцию. Эта функция

  • Постоянный объем работы для проверки базового случая.
  • Работа, необходимая для рекурсивного вызова чего-то наполовину меньше.

Мы можем записать это повторение как

  • T (1) = 1
  • T (n) = 1 + T (n / 2)

Используя тот же трюк, что и раньше, давайте расширимout T (n):

T (n) = 1 + T (n / 2)

= 1 + 1 + T (n / 4)

= 1 + 1 + 1 + T (n / 8)

В общем случае после расширения k раз мы получим

T (n) = k +T (n / 2 k )

Останавливается, когда n / 2 k = 1, что происходит, когда k = log 2 n (то есть lg n).В этом случае мы получаем, что

T (n) = lg n + T (1) = lg n + 1

So T (n) = O (lg n) в этом случае.

Надеюсь, это поможет!

0 голосов
/ 01 марта 2012

Посмотрим теперь .. это добавит 1 к счетчику n раз.каждый вызов n уменьшается вдвое, пока не достигнет единицы.

Вы можете избавиться от цикла и использовать вместо него 

counter+=n;

, поскольку в основном цикл добавляет n к счетчику, 1 на один.

Это означает, что n будет добавляться к счетчику при каждом запуске, а затем уменьшаться на 2, пока не достигнет единицы.

так сказать n = 40. counter: 40 ->60 -> 70 -> 75 -> 77 -> 77. n: 40 -> 20 -> 10 -> 5 -> 2 -> 1.

Просто толчок в правильном направлении (счетчик + = n; будучи важной частью)

...