Базовый рандомизированный алгоритм рекурсии

Question

У меня возникли проблемы с полным пониманием того, как записать повторяемость для ожидаемого времени работы рандомизированного алгоритма.

Я считаю, что я делаю это правильно, но если кто-то сможет его осмотреть, это будет огромной помощью.

Вот псевдокод для алгоритма:

printIntegers(A, n) // an array A of integers is the input, with n integers 
    if A.length > 0 
     for i = 1 to n 
      print A[i] 
     randInt = rand(1, 10) 
     if randInt != 10 
      return 
     else 
      printIntegers(A, n-1) 

Единственной случайная часть генератора случайных чисел от 1 до 10. Я пытаюсь понять, как это будет переводить в рецидиве.

Я имею в виду:

T(n) = O(n)    if a != 10  probability = 9/10 
     T(n-1) + O(n)   a = 10     = 1/10 
     T(n-2) + O(n) 
     .... 
     T(0) + O(n)   

Это имеет смысл в моей голове, а затем ожидаемое время работы будет O (N). Правильно ли я подхожу к этому?

Answer 1

Обратите внимание, что начальное условие должно использовать n в чеке, а не A.length, так как последнее не меняется в рекурсии.

expected количество раз, которое будет называться рекурсия: 0.1. Ожидание такое же, как и вероятность того, что будет вызвана рекурсия. В текущем случае, если генератор случайных чисел действительно случайный, появится число 101/10 времени. Аналогично, ожидаемое количество раз не будет рекурсии - 0.9. Но O(n) появляется в обоих случаях, так что уравнение будет при рассмотрении ожидаемых значений:

T(n) = (0.9 + 0.1) * O(n) + 0.1 * T(n-1) 
    = O(n) + 0.1 * T(n-1) 
    = O(n) + 0.1 * (O(n-1) + 0.1 * T(n-2)) 
    = O(n) + 0.1 * O(n-1) + 0.1^2 * O(n-2) +... 
    = O(n) * (0.1 + 0.1^2 +...+0.1^(n-1)) + 0.1^(n-1) * T(1) 
    = O(n) * (1 - 0.1^n)/0.9 + K 

выше является O(n * (1 - 0.9^n)/0.9), который по существу такой же, как O(n) в зависимости от потребностей вашей точности.

Answer 2

Сначала заметим, что:

T(n) = n + (n-1)/10 + (n-2)/10^2 + ... + 1/10^{n-1} 

Затем, ограничивающая Т (N) выше:

T(n) = n + (n-1)/10 + (n-2)/10^2 + ... + 1/10^{n-1} 
    < n + n/10 + n/10^2 + ... + n/10^{n-1} 
    = n(1 + 1/10 + ... + 1/10^{n-1}) 
    < n(1 + 1/10 + 1/10^2 + ...) 
    = n/(1 - 1/10) = 10n/9 

и ограничивающая его ниже:

T(n) = n + (n-1)/10 + (n-2)/10^2 + ... + 1/10^{n-1} 
    > n 

So n < T(n) < 10n/9 и T(n) является Theta(n).