Найти тэта-обозначение следующего рекурсивного метода - PullRequest
Новая
       43

Найти тэта-обозначение следующего рекурсивного метода

1 голос
/ 04 марта 2012

У меня есть домашний вопрос:

Пусть T (n) обозначает количество раз, когда выражение x = x + 1 выполняется в алгоритме 

example (n)
{
    if (n == 1)
    {
       return
    }
    for i = 1 to n
    {
       x = x + 1
    }
    example (n/2)
}

Найти тэта-обозначение для числа выполнений x = x + 1.(10 баллов).

вот что я сделал:

у нас есть следующий объем работы: - Постоянный объем работы для проверки базового случая - 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)

Я получил этот ответ благодаря thisна вопрос ответил @ templatetypedef

Знайте, что я путаю нотацию с тэтой.ответ будет таким же?Я знаю, что тета-нотация должна ограничивать функцию нижним и верхним пределом.что значит мне нужно функционировать?

1 Ответ

2 голосов
/ 04 марта 2012

Да, ответ будет тот же!

Вы можете легко использовать те же инструменты, чтобы доказать T(n) = Omega(n).

После доказательства T(n) оба O(n) [верхняя асимптотикаграница] и Omega(n) [нижняя асимптотическая граница], вы знаете, что это также Theta(n) [жесткая асимптотическая граница]

В вашем примере легко показать, что T(n) >= n - поскольку это домашняя работа,вам решать, почему.

...