此代码的运行时间是多少

Question

def mystery11(n):
  if n < 1: return n
  def mystery12(n):
    i = 1
    while i < n:
      i *= 2
    return i
  return mystery11(n/2) + mystery11(n/2) + mystery12(n-2)

我对上面的代码有疑问。我完全理解如果没有对 mystery12 的最后一次递归调用，代码 (mystery11) 的运行时间将是 theta(n)。但我不相信每个级别的 theta(log(n)) 工作都在完成。

在第一层，我们做 log(n)，在下一层，我们做 2log(n/2)，然后是 4log(n/4)... 但那不是在每一级看起来像 log(n)（在第二级感觉更接近 2log(n)，在第三级感觉更接近 4log(n) 等等）

我也试过 Wolfram Alpha，我刚刚得到 no solutions exist。但在没有 log(n) 项的情况下工作正常。

那么，这个解是否正确 theta(nlog(n))？如果不是，实际的解决方案是什么？

Ps。抱歉，如果我的 post 中有任何内容不符合礼节，这是我第二次 post 在 Whosebug 上使用。 Post 一个评论，我会修复它。

Answer 1

抱歉，我没听懂你的问题。

我好像不太清楚

不管是什么，

我根据你的'mystery'代码做了数学计算。

假设'm1'是谜11，'m2'是谜12。

没有m2,

时间成本是这样的

m1(n)
= 2*m1(n/2)
= 2*( m1(n/4) + m1(n/4) ) = 4*m1(n/4)
= .....
= 2^k * m1( n / 2^k )

对于使 2^k n 的 k，

2^k = n.

那么 m1(n) 的时间成本是 n * m1(1) = n。

m2的时间成本显然是log(n)

有m2,

时间成本变化如此。

m1(n)
= 2*m1(n/2) + log(n)
= 2*( m1(n/4) + m1(n/4) + log(n) ) + log(n) = 4*m1(n/4) + ( log(n) + 2log(n) )
= ....
= 2^k * m1(n/2^k) + ( log(n) + 2log(n) + 4log(n) ... 2^(k-1)*log(n) )
= 2^k * m1(n/2^k) + log(n) * ∑( 2^(k-1) ) ( where k is from 1 to k )
= 2^k * m1(n/2^k) + log(n)/2 * ∑( 2^k )
= 2^k * m1(n/2^k) + log(n)/2 * ( 2^(k+1) - 1 )
= 2^k * m1(n/2^k) + 2^k * log(n) - log(n)/2

和上一个一样，

对于使 2^k n 的 k，

2^k * m1(n/2^k) + 2^k * log(n) - log(n)/2
= n * m1(1) + n*log(n) - log(n)/2 = n + n*log(n) - log(n)/2

我相信你可以从这里完成剩下的工作。

Ps。如果不是您的要求，我深表歉意。

Answer 2

由于mystery12独立于任何外部函数/变量，我们先来看一下。

在 while-loop、i = 2^j 的第 j 次迭代之后。因此，最大循环数由等式 2^j >= n 或 j = ceil(log2(n)) 给出，其中 ceil 向上舍入到最接近的整数。

现在 mystery11。每个调用包含 2 次使用参数 n / 2 对 mystery11 的递归调用，以及使用参数 n - 2 对 mystery12 的调用。这给出了时间复杂度递归关系（C 是某个正常数）：

您已经正确推导出递归深度为m ~ log n。精确值为m = ceil(log2(n))。利用四舍五入后的数字与自身相差小于 1 的事实，我们可以消除一些圆括号：

让我们先检查一下B。问题出现了——对数里面的表达式可以是负数。 while-loop mystery12 never 如果 n - 2 < 1 执行 - 即它的复杂性可以被截断为 O(1)这个边缘案例。因此，总和由上限定为：

这里我们使用了 log 的泰勒展开式。因此 B 在我们的分析中可以忽略，因为它已经被第一项所掩盖。

现在检查A。这是一个有点乏味的总结，我将使用 Wolfram Alpha 来计算：

Therefore the overal time complexity of mystery11 is Θ(n), not Θ(n log n) as predicted.

这是为什么？原因就在于"each recursive call does log n work"——这里的n和传给mystery11的n的初始值不一样（[=73=中的n ]总体时间复杂度）。在每个递归级别 n 呈指数递减，因此：

We cannot naively multiply the amount of work done per call with the number of recursive calls.

这通常适用于复杂性分析。

此代码的运行时间是多少

What is the runtime for this code

python

runtime

time-complexity

asymptotic-complexity

orders