Как перейти от рекуррентного отношения к конечной сложности

Question

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

//Input: Adjacency matrix A[1..n, 1..n]) of an undirected graph G  
//Output: 1 (true) if G is complete and 0 (false) otherwise  
GraphComplete(A[1..n, 1..n]) {
  if ( n = 1 )
    return 1 //one-vertex graph is complete by definition  
  else  
    if not GraphComplete(A[0..n − 1, 0..n − 1]) 
      return 0  
    else 
      for ( j ← 1 to n − 1 ) do  
        if ( A[n, j] = 0 ) 
          return 0  
      end
      return 1
}

Вот то, что я считаю допустимым и корректным рекуррентным соотношением:

$\qquad \begin{выровнять} T (1) &= 0 \\ T(n) &= T(n-1) + n - 1 \quad ext{для } n \geq 2 \конец{выровнять}$

"$n - 1 $" - это сколько раз выполняется тело цикла for, в частности проверка "if A[n,j]= 0".

Проблема в том, куда мне теперь идти?Как мне преобразовать вышесказанное во что-то, что на самом деле показывает, какова результирующая сложность?

Answer 1

Из того, что вы написали, кажется, что для всех $ k $ у вас есть $ t (k) = k-1+t (k-1) $ и $ t (1) = 0 $. Поэтому вы можете получить его напрямую:

$$ t (n) = (n-1)+(n-2)+ dots+1+0 = sum_ {k = 1}^{n} {(k-1)} = frac {n ( n-1)} {2} $$

Так $ t (n) $ в $ Θ (n^2) $.

Answer 2

Рекурсия, которая у вас там есть, такова, если мы учитываем только обращения к матрице:

$\qquad \begin{выровнять} T (1) &= 0 \\ T(n) &= T(n-1) + n - 1 \quad ext{для } n \geq 2 \конец{выровнять}$

Обратите внимание, что это только верхняя граница функции времени выполнения, поскольку цикл выполняется не всегда.Это линейный рекуррентное соотношение, и существуют многими способами о решении этих проблем.Вероятно, вы можете развернуть $ T (n) $, найти закономерность и доказать это методом индукции.Однако это не всегда срабатывает, вот почему я хочу представить общую технику.

Это мой любимый способ - использовать генерирующие функции.Он использует только механический расчет (как только вы привыкнете к такому подходу).Это и есть анзац:

$\qquad \begin{выровнять} \mathcal{T}(z) &= \sum_{n=1} ^\infty T(n)z ^n \\ &= 0 + \сумма_{n=2}^\через T(n) z^n \\ &= \sum_{n=2}^\infty (T(n-1) + n - 1)z^ n \\ &= \sum_{n=2}^\infty T(n-1)z ^ n + \sum_{n=2}^\infty (n-1) z ^ n \\ &= z\sum_{n=2}^\infty T(n-1)z^{n-1} + z\sum_{n=2}^\infty (n-1)z^{n-1} \\ &= z\sum_{n=1}^\infty T(n)z^{n} + z\sum_{n=1}^\infty nz^{n} \\ &= z\mathcal{T}(z) + z\cdot\frac{z}{(1-z)^2} \end{выровнять}$

Идентификационные данные, необходимые для последнего шага, см. в разделе Шпаргалка TCS.Если мы теперь решим это уравнение для $ \ mathcal {T} $, то получим:

$\qquad \displaystyle \begin{выровнять} \mathcal {T}(z) &= \frac{z^ 2}{(1-z) ^ 3} \\ &= z^ 2\сумма_{n= 0}^\ бесконечность \ бином{n+ 2}{n} z ^ n \\ &= \sum_{n=0}^\infty \frac{(n+ 2)(n+ 1)}{2}z^{n+2} \\ &= \sum_{n=2}^\infty \frac{n(n-1)}{2}z^{n} \\ &= \sum_{n=1}^\infty \frac{n(n-1)}{2}z ^{n} \\ \end{выровнять}$

Для первого шага еще раз ознакомьтесь со Шпаргалкой.Помните, что мы начали с $ \ mathcal {T}(z) = \sum_ {n = 1} ^\infty T (n) z ^ n $, чтобы мы могли прочитать решение с последней строки:

$\qquad \displaystyle T(n) = \frac{n(n-1)}{2} \in \ Theta(n ^ 2)$