Большой O рекурсивных методов

Мне трудно определить большой O простых рекурсивных методов. Я не могу оборачивать голову тем, что происходит, когда метод вызывается несколько раз. Я бы более подробно рассказал о своих путаницах, но на данный момент я пытаюсь ответить на некоторые вопросы, и вместо того, чтобы не обманывать, я прошу, чтобы кто-то, кто отвечал на это сообщение, придумал простой рекурсивный метод и обеспечивают простое объяснение большого O указанного метода. (Желательно на Java... язык, который я изучаю.)

Спасибо.

Ответ 1

Вы также можете определить порядок рекурсивно. Например, скажем, у вас есть функция f. Для вычисления f (n) выполняется k шагов. Теперь вы хотите вычислить f (n + 1). Предположим, что f (n + 1) вызывает f (n) один раз, то f (n + 1) принимает k + некоторые постоянные шаги. Каждый вызов будет выполнять некоторые дополнительные шаги, поэтому этот метод O (n).

Теперь посмотрим на другой пример. Допустим, вы внедряете фибоначчи наивно, добавляя два предыдущих результата:

fib(n) = { return fib(n-1) + fib(n-2) }

Теперь скажем, вы можете рассчитать fib (n-2) и fib (n-1) как в около k шагов. Для вычисления fib (n) вам нужны k + k = 2 * k шагов. Теперь скажем, что вы хотите рассчитать fib (n + 1). Таким образом, вам понадобится в два раза больше шагов, чем для fib (n-1). Таким образом, это, по-видимому, O (2 ^ N)

По общему признанию, это не очень формально, но, надеюсь, таким образом вы можете немного почувствовать себя.

Ответ 2

Вы можете обратиться к основной теореме для поиска больших O рекурсивных методов. Вот статья в википедии: http://en.wikipedia.org/wiki/Master_theorem

Вы хотите думать о рекурсивной проблеме, подобной дереву. Затем рассмотрите каждый уровень дерева и объем требуемой работы. Обычно проблемы делятся на 3 категории: тяжелый корень (первая итерация → остаток дерева), сбалансированный (каждый уровень имеет равное количество работы), тяжелый лист (последняя итерация → остальная часть дерева).

Взятие сортировки слияния в качестве примера:

define mergeSort(list toSort):
    if(length of toSort <= 1):
        return toSort
    list left = toSort from [0, length of toSort/2)
    list right = toSort from [length of toSort/2, length of toSort)
    merge(mergeSort(left), mergeSort(right))

Вы можете видеть, что каждый вызов mergeSort, в свою очередь, вызывает еще 2 mergeSorts из 1/2 первоначальной длины. Мы знаем, что процедура слияния займет время, пропорциональное количеству слитых значений.

Рекуррентное соотношение тогда T (n) = 2 * T (n/2) + O (n). Два из двух вызовов, а n/2 - от каждого вызова, имеющего только половину количества элементов. Однако на каждом уровне существует одинаковое количество элементов n, которые необходимо объединить, поэтому постоянная работа на каждом уровне равна O (n).

Мы знаем, что работа распределена равномерно (O (n) каждая глубина), а дерево log_2 (n) глубокое, поэтому большая O рекурсивной функции O (n * log (n)).