时间戳

首页 > 解决方案 > 计算递归函数的时间复杂度

time-complexity - 计算递归函数的时间复杂度

问题描述

.0 < c < 1 ,T(n) = T(cn) + T((1 - c)n) + 1

基本级别：如果（n<=1）返回；数据类型 - 正整数

我必须找到这个递归函数的 Big-Theta 函数。我试图开发递归方程，但它从一个层次到另一个层次变得复杂，并且看不到任何形式。

我也试过这个 - 假设 c<(1-c). 所以 - 2T(cn) + 1 <= T(cn) + T((1-c)n)+1 <= 2T((1-c)n)+1

它给了我一些下限和上限，但不是 theta 界:(

标签： time-complexity

解决方案

当 c 接近 0 或 1 时，递归接近 T(n) = T(n-1) + 2（假设 T(0) = 1 也是如此）。对于 n > 0，这具有线性函数 T(n) = 2n - 1 作为解。

对于 c = 1/2，递归变为 T(n) = 2T(n/2) + 1。看起来 T(n) = 2n - 1 是 n > 0 的解决方案。

这似乎有力地证明了函数 T(n) = 2n - 1 是所有 c 的解：它在两端和中间都有效。如果我们分...

2n - 1 = 2cn - 1 + 2(1-c)n - 1 + 1 
       = 2cn - 1 + 2n - 2cn - 1 + 1
       = 2n - 1

我们发现 T(n) = 2n - 1 是一般情况的解。

推荐阅读