Блог

Здесь у меня есть такая функция, и я хочу найти рекурсивное отношение к ней, а после этого вычислить временную сложность этого рекурсивного отношения.

  public static void f(int n) {
    if (n == 1) {
        //" Do sth "
    } else {
        for (int i = 1; i < n; i  ) {
            f(i - 1);
            //" Do sth "
        }
    }
}
  

на самом деле я много пытался для этого, и я получил T (n) = n * f (n-1) для этой функции в качестве отношения, но я не уверен в этом. не могли бы вы помочь мне найти правильное отношение и решить его?

Предполагая, что T(1) = «Do sth» является постоянной работой, т. Е. Не зависит от размера ввода n , вы можете записать рекурсивную функцию времени как :

 T(n) =  T(1)   T(2)   ...   T(n-1)
     =  { T(1) }    { T(1) }   { T(1)   T(2) }   { T(1)   T(2)   T(3) }   { T(1)   T(2)   T(3)   T(4) }  ....

     [let T(1) = x]

     =  x   x   {x   x}   {x   x   (x   x)}   {x   x   (x   x)   x   x   (x   x)}  ....

     = x   x   2x   4x   8x   ...

     ~ x.2^(n-2)

     ~ O(2^n)
  

Вот программа на python для демонстрации последовательности коэффициентов для суммирования:

 t = [0 for i in range(10)]
for i in range(1,10):
  if i == 1:
    t[i] = 1
  else:
    val = 0
    for j in range(1,i):
      val  = t[j]
    t[i] = val
print(t[1:])
  

печатает : [1, 1, 2, 4, 8, 16, 32, 64, 128]

Вы можете видеть, что 2 ^(n-2) для n> = 2 выполняется при каждом ‘n’, а сложность равна O (2 ⁿ)