algorithm - 如何找到根据立方根定义步骤的递归的复杂性？

Question

T(1) = 1

T(n) = T(n^1/3) + 1

我该如何解决？“解决”我的意思是找到它的“复杂性”（我真的不知道用英语怎么说），例如 O(nlogn) ecc。

我猜不出替换方法；我用迭代方法无处可去，我不能应用主定理。

我到了这里，但我不确定：

T(n) = T(n^(1/3^k))) +k

你能给我和建议吗？

score 5 · Accepted Answer

我将尝试制定一些可能的解决方案。您可以根据进一步的限制选择一个。

递归将一直运行直到n变为1。这是：

1 = n^(1/3^k)

或更一般地说

b = n^(1/3^k)

哪里k是递归深度。解决这个问题k：

ln(b) = 1/3^k * ln(n)
ln(ln(b) / ln(n)) = k * ln(1/3)
-ln(ln(b) / ln(n)) / ln(3) = k

如果我们设置b为 1，则方程变得不可解，因为ln(0)未指定。这相当于无限递归。

但是，我们可以说在最后一次递归中n应该是“大约 1”。所以我们实际上有一个b != 1. 那么 k 是：

k = -ln(ln(b) / ln(n)) / ln(3)
  = -ln(c1 / ln(n)) / c2
  = -(ln(c1) - lnln(n)) / c2
  = (-c3 + lnln(n)) / c2

这应该是O(log log n)。

如果你想截断n到它的整数部分，计算会变得非常混乱，因为你在每一步之后都有特殊情况。但是，我们可以通过指定来近似结果b = 1.999999。这将产生与上述相同的复杂性。

score 1 · Accepted Answer

如果这是一个递归函数，那么我所理解的是 T(n)= T(integerpart(cubicsquare(n)) +1 ;

在这种情况下：

S=0;
if (n>=1){
S++;
N= n;
while  (N>1){
N=integerpart(N^1/3);
S++;
}

}
T(n)= S ;

这意味着 T(n) 是一个简单的函数：具有整数界限，keme 间隔的宽度为 2^(3^k) - 2^(3^(k-1))

你可以看到，第一个区间是 if n in ]1,8[ T(n)=2; 那么如果 n in [8,252[ ,T(n)=3... 所以，我们可以说 t(2^(3^k)) = k+1 ；然后 t(n) ~O(ln(ln(n))/ln(3)) （考虑套件 2^3^k）

2 回答 2