Написать рекуррентное отношение функции - PullRequest
Новая
       71

Написать рекуррентное отношение функции

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

Я знаю формулу для рекуррентного соотношения: T (n) = aT (n / b) + f (n). И учитывая это уравнение, я знаю, как решить для BigO. Мой домашний вопрос попросил меня написать рекурсивную функцию для подсчета количества узлов в списке, что я и сделал, но затем попросил меня написать рекуррентное отношение. Вот мой код: 

int count(ListNode *l)
{
    if(!l) return 0;
    if(!l->next) return 1;

    return 1 + count(l->getNext());
}

Но я полностью заблудился о том, как создать / сформулировать мою собственную формулу отношения повторения ... как мне найти a или b .... Я не знаю, с чего начать. Как мне написать рекуррентное отношение для этой функции? Спасибо.

Ответы [ 2 ]

5 голосов
/ 05 марта 2012

Ваше первое рекуррентное отношение обычно используется для описания времени выполнения алгоритмов разделяй и властвуй .a здесь показывает, на сколько частей вы делите свои данные, 1/b показывает, какая часть исходных данных используется в каждой части, а f(n) показывает, сколько времени вам нужно на каждом «уровне».Например, в алгоритме QuickSort вы делите свои данные (массив или список) на 2 части, каждая из которых составляет ровно половину (1/2) исходных данных, и на каждом «уровне» деления вам нужно пройти все n элементы 1 раз.Таким образом, рекуррентное отношение равно 

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

(которое оценивается как O (n * lg (n))). И в бинарном поиске вы делите данные на 2 части, но занимает только 1 из них, и время на каждую "level "является константой, поэтому отношение равно: 

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

Однако ваша функция в C не следует стратегии" разделяй и властвуй ".Вместо этого он демонстрирует математическую индукцию .Вы определяете начальные условия: если l равно NULL, то длина равна 0, а если l->next равно NULL (вы также определяете условие для 1 элемента в списке).Затем вы определяете своего рода индуктивный шаг - вы определяете, как вычислить функцию для n-го элемента, если вы знаете значение функции для (n - 1) -го элемента.Итак, зная значение функции для 1-го элемента, вы можете применить это правило и получить значение для 2-го элемента, затем для 3-го и так далее.

Итак, вы можете видеть, что индукционный метод по своей природе является алгоритмом повторения.Здесь мы должны рассмотреть 2 раза.Первый - это время для вычисления значения в начальной точке (или конечной точке - это зависит от порядка, в котором вы смотрите список).В вашей функции вы просто возвращаете это значение, поэтому оно является постоянным (C1).Второй - это время сделать 1 шаг.В вашей функции она также постоянна (C2).Интуитивно вы должны видеть, что время выполнения этого алгоритма будет: 

T(n) = C1, when n = 1 
T(n) = T(n - 1) + C2, when n > 1

Таким образом, если только n = 1, вы не определите время выполнения алгоритма на элементе n через время, чтобы выполнить его на элементах n - 1,В нотации BigO любая константа определяется как 1, а регистр 1 элемента не рассматривается, поэтому ваше окончательное отношение повторения: 

T(n) = T(n - 1) + 1

(которое оценивается как T(n) = T(n - 1) + 1 = T(n - 2) + 2 = ... = 1 + n или O(n))

Дополнительная литература :

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

Я давно не писал рекуррентных отношений, но это должен быть ответ: T (n) = T (n-1) + ПОСТОЯННАЯ. Ваша формула: T (n) = aT (n / b) + f (n). б: вы делите проблему на б части. f (n): сколько времени используется для решения проблемы a: номер экземпляра проблемы В твоей проблеме Вы линейно уменьшаете задачу на 1., так что это n-1. Константа подразумевает, что для решения проблемы требуется некоторое ПОСТОЯННОЕ время

PS: я не использовал рекуррентное отношение с 8 лет, но это так.

...