난수로 재귀 호출

Question

function foo(n) 
    if n = 1 then 
     return 1 
    else 
     return foo(rand(1, n)) 
    end if 
    end function 

foo가 처음에 매개 변수로 m과 함께 호출되면, rand()가 호출되는 예상 횟수는 얼마입니까?

BTW, rand (1, n)은 1에서 n 사이의 균일하게 분포 된 임의의 정수를 반환합니다.

Answer 1

간단한 예제는 f(2)을 계산하는 데 걸리는 호출 수입니다. 이번에는 x이고, 다음에 x = 1 + 0/2 + x/2이라고하고 실제 전화 1을 입력하면 확률이 1/2이되고 f(1)으로 가고 확률은 입니다. 방정식을 풀면 x = 2이됩니다.

대부분의 실행 시간 분석에서와 마찬가지로 실행 시간에 대한 재귀 수식을 얻으려고합니다. 따라서

E[T(1)] = 0 
E[T(2)] = 1 + (E[T(1)] + E[T(2)])/2 = 2 
E[T(n)] = 1 + (E[T(1)] + E[T(2)] + ... E[T(n)])/n 
     = 1 + (E[T(1)] + E[T(2)] + ... E[T(n-1)])/n + E[T(n)]/n 
     = 1 + (E[T(n-1)] - 1)(n-1)/n + E[T(n)]/n 

E[T(n)](n-1) = n + (E[T(n-1)] - 1)(n-1) 

그래서, n> 1 :

E[T(n)] = 1/(n-1) + E[T(n-1)] 
     = 1/(n-1) + 1/(n-2) + ... + 1/2 + 2 
     = Harmonic(n-1) + 1 
     = O(log n) 

이것은 또한 우리가 직관적으로 수도 인 우리는 무작위로 호출을 통해 진행하는 기대의 선형성을 사용할 수 있습니다 n이 f로 전화 할 때마다 약 절반이되어야하기 때문에 예상했습니다.

우리는 '높은 확률로 최악의 경우'를 고려할 수도 있습니다. 이를 위해 Markov의 불평등을 쉽게 사용할 수 있습니다 (P[X <= a*E[X]] >= 1-1/a). a = 100을 설정하면 99 %의 확률로 알고리즘이 100 * log n보다 작게 rand으로 전화를 겁니다.