代码之家 › 专栏 › 技术社区 › Thomas

此代码的运行时是什么

orders asymptotic-complexity time-complexity runtime python

-1

Thomas · 技术社区 · 8 年前

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)。但我不相信在每一个层次上,θ(log(n))的工作都在进行。

在第一级,我们做log(n),在下一级,我们做2log(n/2),然后做4log(n/4)。。。但这并不像每个级别上的log(n)(第二级感觉更接近2log(n),第三级感觉更接近4log(n),等等)

我也试过Wolfram Alpha no solutions exist 。但在没有对数(n)项的情况下效果很好。

那么,这个解是否正确θ(nlog(n))?如果没有,实际的解决方案是什么?

如果我的帖子中有任何不符合礼仪的地方,请道歉,这是我第二次在Stackoverflow上发布。发表评论,我会修复它。

2 回复 | 直到 8 年前

meowgoesthedog 8 年前

自从 mystery12 独立于任何外部函数/变量,让我们先看看它。

在 j -while循环的第次迭代, i = 2^j 。因此,最大循环数由方程式给出 2^j >= n 或 j = ceil(log2(n)) 哪里 ceil 四舍五入到最接近的整数。

现在用于 mystery11 。每个调用包含2个递归调用 神秘11 带参数 n / 2 ,并致电 神秘12 带参数 n - 2 。这给出了时间复杂度递推关系( C 是某个正常数):

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

让我们检查一下 B 第一出现了一个问题-对数内的表达式可能是负数。while循环 神秘12 从不如果执行 n - 2 < 1 -即,其复杂性可以截断为 O(1) 在这种边缘情况下。因此,总和为 从上方开始 签署人:

我们用泰勒展开式 log 。因此 B 在我们的分析中可以忽略,因为它已经被第一个术语所掩盖。

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

因此 神秘11 是 Î(n) 不 Î(n log n) 正如预测的那样。

为什么会这样?原因在于“每个递归调用 log n “工作”- n 此处与的初始值不同 n 传递给 神秘11 (the n 在 全面的 时间复杂性)。在每个递归级别 n 指数递减,因此:

我们不能天真地将每个调用完成的工作量与递归调用的数量相乘。

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

Al.T.Os 8 年前

对不起,我不明白你的问题是什么。

我似乎不太清楚。

不管是什么,

我是根据你的“神秘”密码计算的。

假设‘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

我相信你可以在这里完成剩下的事情。

另外,如果不是你要求的,我很抱歉。