Анализ временной и пространственной сложности рекурсивных задач

структура данных

Временная/пространственная сложность рекурсии

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

Основы рекурсии

  1. Базовый вариант.Случай, который можно решить без рекурсии.
  2. продолжайте продвигаться.Убедитесь, что каждый рекурсивный вызов уменьшает размер проблемы до базового случая.
  3. правила оформления.Предположим, что все рекурсивные вызовы работают.
  4. Закон синтетической выгоды.Никогда не выполняйте повторяющуюся работу в разных рекурсивных вызовах. Это правило может привести крекурсия запоминания.

Несколько общих рекурсивных алгоритмов

обход дерева

void printInorder(TreeNode root){
	if(root == null) return;
    printInorder(root.left);
    System.out.println(root.val);
    printInorder(root.right);
}

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

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

Time: T(n) = 2 * T(n / 2) + O(1) --> T(n) = O(n)

Space: O(logn) --> O(h) h--> the height of the tree

бинарный поиск

def binary_search(a, l, r):
	m = (l + r) / 2
	if(f(m)):
		binary_search(a, l, m)
	else:
		binary_search(a, m + 1, r)

Time: T(n) = T(n / 2) + O(1) --> T(n) = O(logn)

Space: O(logn)

быстрая сортировка

def qucik_sort(a, l, r):
	pivot = patition(a, l, r)	# Time: O(r - l)
	quick_sort(a, l, p)
	quick_sort(a, p + 1, r)

Поскольку производительность быстрой сортировки зависит от опорного элементаpivot, так что есть наихудший сценарий наилучшего случая.Best case: T(n) = 2 * T(n / 2) + O(n)

согласно сосновной метод,T(n) = O(nlogn)

Worst case: T(n) = T(n - 1) + T(1) + O(n) --> T(n) = O(n ^ 2)

Space: O(logn) --> O(n)

Сортировка слиянием

def merge_sort(a, l, r):
	m = (l + r) / 2
	merge_sort(a, l, m)
	merge_sort(a, m + 1, r)
	merge(a, l, m, r) 	# O(r - l)

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

Однако, поскольку слияние требует операции копирования массива, быстрая сортировка больше использует систему, а наихудший случай встречается редко, поэтому быстрая сортировка используется более широко.

Time: T(n) = 2 \* T(n / 2) + O(n) --> T(n) = O(nlogn)

Space: O(logn + n) --> 递归深度O(logn), 拷贝数组 O(n)

Combination

def conbination(d, s):
	if(d == n):
		return func()	#O(1)
	for i in range(d + 1, n):
		combination(d + 1, i + 1)

Time: T(n) = T(n - 1) + T(n - 2) + ... + T(1) --> O(2^n)

Space: O(n)

Permutation

def permutation(d, used):
	if(d == n):
		return func()	#O(1)
	for i in range(0, n):
		if i in used: continue
		used.add(i)
		permutation(d + 1, used)
		used.remove(i)

Time: T(n) = n * T(n - 1) --> O(n!)

Space: O(n)

Сводная форма

Equation Time Space Examples
T(n) = 2 * T(n / 2) + O(n) O(nlogn) O(logn) qucik_sort
T(n) = 2 * T(n / 2) + O(n) O(nlogn) O(logn + n) merge_sort
T(n) = T(n / 2) + O(1) O(logn) O(logn) binary_search
T(n) = 2 * T(n / 2) + O(1) O(nlogn) O(logn) binary tree
T(n) = T(n - 1) + O(1) O(n^2) O(n) quick_sort (worst case)
T(n) = n * T(n - 1) O(n!) O(n) permutation
T(n) = T(n - 1) + T(n - 2) + ... + T(1) O(2^n) O(n) combination

Рекурсия запоминания

Согласно вышеупомянутому четвертому правилу рекурсии, закону синтетической выгоды, давайте посмотрим на эту последовательность Фибоначчи.

def fib(n):
	if n < 3 : return 1
	return fib(n - 1) + fib(n - 2)

Time: T(n) = T(n - 1) + T(n - 2) + ... + T(1) = O(2^n) = O(1.618^n)

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

def fib(n):
	if(n < 3): return 1
	if memo[n] > 0: return memo[n]
	memo[n] = fib(n - 1) + fib(n - 2)
	return memo[n]

из которых памятьmemoЕго можно сохранить в глобальной переменной или передать как параметр функции. При анализе временной и пространственной сложности мемоизированной рекурсии обычно нужно только увидеть, сколько подзадач она содержит. Пространство также пропорционально размеру памяти.

Time: O(n)

Space: O(n)

Для более сложных случаев попробуйте использоватьосновной методИли способ рекурсивного дерева вывести.

Категории