Блог

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

Например:

 FindMin(int A[], int front, int last)

if (last-front <= 1) 
  return A[front]
else {
  midpoint = (front last)/2
  int minFront = FindMin(A, front, midpoint)
  minLast =  FindMin(A, midpoint 1, last)
  return min{minFront, minLast}
}
  

Если кто-нибудь может помочь мне определить рекуррентное отношение для этой функции / функции, подобной ей, и проведет меня через шаги по определению отношения, я поцелую ваши сапоги (не совсем, но ваша помощь будет очень признательна).

Ваша рекурсия описывается простой зависимостью, потому что вы делите задачу на две равные подзадачи и выполняете постоянное количество операций:

 T(n) = 2 * T(n/2)   C
T(n) = 2 * (2 * T(n/4)   C)   C = 4 * T(n/4)   3*C
T(n) = 4 * (2 * T(n/8)   C)   3*C = 8 * T(n/8)   7*C
...
T(n) = n * T(1)   (n-1)*C = n * C = O(n)
  

Обратите внимание, что глубина стека для этой рекурсии равна log (N), поэтому сложность пространства равна O (log (N))
(благодаря дополнению Абхишека Бансала)