算法分析 : Expected Running Time of Recursive Function Based on a RNG

Question

我对此处程序的运行时间分析有些困惑，该程序具有依赖于 RNG 的递归调用。 (随机生成的数字)

让我们从伪代码开始，然后我将讨论到目前为止我所想到的与此相关的内容。

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);

好的，现在让我们进入我到目前为止尝试过的数学。我会尽量不要在这里过于迂腐，因为它只是对预期运行时间的粗略估计分析。

首先，让我们考虑最坏的情况。请注意，K = Random(n) 必须至少为 1，并且最多为 n。因此，最坏的情况是 K = 1 被选中。这导致总运行时间等于 T(n) = cn + T(1) + T(n-1)。这意味着总的来说它总共需要大约 cn^2 的时间(如果你对递归关系卡住或生疏，你可以使用 Wolfram 来解决递归关系，尽管这是一个相当简单的问题)。

现在，这是我有点困惑的地方。对于预期的运行时间，我们必须根据随机数 K 的概率进行假设。因此，我们必须将不同 k 值的所有可能运行时间加上它们各自的概率相加。通过引理/希望直观的逻辑:任何一个随机生成的 k 的概率，其中 k 在 1 到 n 之间，等于 1/n。

因此，(在我看来/分析中)预期的运行时间是:

ET(n) = cn + (1/n)* (k=1 to n-1) of (ET(k-1) + ET(n-k))

让我稍微解释一下。 cn 只是用于运行 i 到 j 的循环。这是cn估计的。总和表示 k 的所有可能值。 (1/n) 乘以这个总和是因为任何一个 k 的概率是 (1/n)。 求和里面的项表示Func1递归调用的运行时间。左边第一项取ET(k-1)，因为这个递归调用要从i到k循环-1(大致是 ck)，然后可能再次调用 Func1。第二个是第二次递归调用的表示，将从 i+k 循环到 j，也用 n-k 表示。

展开求和后，我们看到整体函数 ET(n) 的阶数为 n^2。 但是，作为测试用例，插入k=(n/2) 给出 Func 1 的总运行时间大约为 nlog(n)。 这就是我困惑的原因。如果估计的运行时间是 n^2 阶，这怎么可能呢？我是否通过为 k 插入 n/2 来考虑“好”情况？还是我以某种方式错误地考虑了 k ？

Answer 1

预期的时间复杂度是 ET(n) = O(nlogn) 。以下是我自己得出的数学证明，如有错误请指出:-

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)