算法分析：基于一个RNG预计运行时间递归函数的 [英] Algorithm Analysis: Expected Running Time of Recursive Function Based on a RNG

问题描述

我在这里一个程序，它具有依赖于RNG递归调用的运行时间分析有些困惑。 （随机生成的号码）

I am somewhat confused with the running time analysis of a program here which has recursive calls which depend on a RNG. (Randomly Generated Number)

让我们开始与伪code，然后我会去到什么，我曾经想过到目前为止，与此相关的。

Let's begin with the pseudo-code, and then I will go into what I have thought about so far related to this one.

Func1(A, i, j)
/* A is an array of at least j integers */

1 if (i ≥ j) then return (0);
2 n ← j − i + 1 ; /* n = number of elements from i to j */
3 k ← Random(n);
4 s ← 0; //Takes time of Arbitrary C

5 for r ← i to j do
6 A[r] ← A[r] − A[i] − A[j]; //Arbitrary C
7 s ← s + A[r]; //Arbitrary C
8 end

9 s ← s + Func1(A, i, i+k-1); //Recursive Call 1
10 s ← s + Func1(A, i+k, j); //Recursive Call 2
11 return (s);

好了，现在让我们来看看我已经试过到目前为止数学。我会尽量不要太迂腐这里，因为它仅仅是预期的运行时间比较粗糙，估计分析。

Okay, now let's get into the math I have tried so far. I'll try not to be too pedantic here as it is just a rough, estimated analysis of expected run time.

首先，让我们考虑最坏的情况。注意，K =随机（正）必须至少为1，和最多n。因此，最坏的情况是在K = 1被拾取。这导致总运行时间为等于到T（n）= CN + T（1）+ T（N-1）。这意味着，总体而言，它需要大约CN ^ 2时总的地方（可以使用钨来解决递推关系，如果你被卡住或生锈的递推关系，虽然这个人是一个相当简单的一个）。

First, let's consider the worst case. Note that the K = Random(n) must be at least 1, and at most n. Therefore, the worst case is the K = 1 is picked. This causes the total running time to be equal to T(n) = cn + T(1) + T(n-1). Which means that overall it takes somewhere around cn^2 time total (you can use Wolfram to solve recurrence relations if you are stuck or rusty on recurrence relations, although this one is a fairly simple one).

现在，这里是我得到有些困惑。对于预计运行时间，我们必须将我们的假设关闭随机数K的概率。因此，我们要总结所有可能的运行时间不同的k值，以及它们各自的概率。通过引理/希望直观逻辑：中的任何一个随机产生k中的概率，以1之间k以N，等于1 / N。

Now, here is where I get somewhat confused. For the expected running time, we have to base our assumption off of the probability of the random number K. Therefore, we have to sum all the possible running times for different values of k, plus their individual probability. By lemma/hopefully intuitive logic: the probability of any one Randomly Generated k, with k between 1 to n, is equal 1/n.

因此，（在我看来/分析）预计运行时间为：

ET（N）= CN +（1 / N）*总和（从K = 1到n-1）（ET（K-1）+ ET（NK））

让我来解释一下。可换股票据是只是为它运行i到j循环。这个估计被CN。求和再presents所有K的可能值。的（1 / n）的乘积求和是有，因为任一项k的概率为（1 / n）中。 里面的总和，再present条款FUNC1的递归调用的运行时间。左边的第一项采用ET（K-1），因为这递归调用将会做一个循环从i到k-1（其大致CK），然后可能再次调用FUNC1。二是重presentation第二递归调用，这将循环从i + K到j，这也再次被NK psented $ P $。

Let me explain a bit. The cn is simply for the loop which runs i to j. This is estimated by cn. The summation represents all of the possible values for k. The (1/n) multiplied by this summation is there because the probability of any one k is (1/n). The terms inside the summation represent the running times of the recursive calls of Func1. The first term on the left takes ET(k-1) because this recursive call is going to do a loop from i to k-1 (which is roughly ck), and then possibly call Func1 again. The second is a representation of the second recursive call, which would loop from i+k to j, which is also represented by n-k.

一旦扩张的总和，我们看到，整体功能ET（n）是n阶^ 2。 然而的，作为一个测试的情况下，插入K =（N / 2）给出的总的运行时间为函数功能1大致n日志（n）的。 此的就是为什么我很困惑。这怎么可能，如果估计的运行时间是n阶^ 2的？我是否考虑好的情况下，通过插入N / 2对于k？还是我以某种方式思考K的错误的意义吗？

Upon expansion of the summation, we see that the overall function ET(n) is of the order n^2. However, as a test case, plugging in k=(n/2) gives a total running time for Func 1 of roughly nlog(n). This is why I am confused. How can this be, if the estimated running time is of the order n^2? Am I considering a "good" case by plugging in n/2 for k? Or am I thinking about k in the wrong sense in some way?

推荐答案

预计时间复杂度为 ET（N）= O（nlogn）。以下是数学证明我自己推导，请告诉我们，如果任何错误： -

Expected time complexity is ET(n) = O(nlogn) . Following is math proof derived by myself please tell if any error :-

ET(n) = P(k=1)*(ET(1)+ET(n-1)) + P(k=2)*(ET(2)+ET(n-2)).......P(k=n-1)*(ET(n-1)+ET(1)) + c*n

As the RNG is uniformly random  P(k=x) = 1/n for all x

hence ET(n) = 1/n*(ET(1)*2+ET(2)*2....ET(n-1)*2) + c*n

ET(n) = 2/n*sum(ET(i)) + c*n i in (1,n-1)

ET(n-1) = 2/(n-1)*sum(ET(i)) + c*(n-1) i in (1,n-2)

sum(ET(i)) i in (1,n-2) = (ET(n-1)-c*(n-1))*(n-1)/2

ET(n) = 2/n*(sum(ET(i)) in (1,n-2) + ET(n-1)) + c*n

ET(n) = 2/n*((ET(n-1)-c*(n-1))*(n-1)/2+ET(n-1)) + c*n

ET(n) = 2/n*((n+1)/2*ET(n-1) - c*(n-1)*(n-1)/2) + c*n

ET(n) = (n+1)/n*ET(n-1) +  c*n - c*(n-1)*(n-1)/n

ET(n) = (n+1)/n*ET(n-1) + c

solving recurrence

ET(n) = (n+1)ET(1) + c + (n+1)/n*c + (n+1)/(n-1)*c + (n+1)/(n-2)*c.....


ET(n) = (n+1) + c + (n+1)*sum(1/i) i in (1,n)


sum(1/i) i in (1,n) = O(logn)


ET(n) = (n+1) + c + (n+1)*logn


ET(n) = O(nlogn)

这篇关于算法分析：基于一个RNG预计运行时间递归函数的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！