形式T（n）的递归= T（n-n ^（1 / q））

Question

我正在尝试找到以下问题的答案：

T(n) = T(n - n^(1/q)), q > 2
T(c) = O(1), for a constant c

我感兴趣的是递归问题，这些问题不会分支并且没有任何辅助计算。类似于this problem。区别在于，在每次递归调用中，减少我的问题的数量也会减少。我试图通过一种迭代方法来解决这个问题：

T(n) = T(n - n^(1/q) = 
     = T[n - n^(1/q) - [n - n^(1/q)]^(1/q)] = 
     = ....

我无法真正找到一个合理的扩展。为此，我尝试了T(n) \in O(n)和T(n) \in O(log(n))的替换方法，如果我没有犯任何错误，这两种方法都适用。

鉴于我现在只能假设T(n) = T(n - n^(1/q)) \in O(log(n)), for q > 2，这似乎很合理，因为它与二进制搜索非常相似。

可悲的是，我还没有真正介绍过此类递归，我也不了解遵循此类递归的应用程序。

鉴于我所有的问题是：

我们是否可以推理不会分支且没有与上述陈述可比的辅助计算的递归问题？

具有这种行为的算法是否有应用？我猜想它可能在线性字段中搜索时出现，与二进制搜索非常相似，但不能将字段切成两半？

类似的问题如下：T(n) = x + T(n-log(n))和T(n) = x + T(n-log(n))

编辑：删除了错误的扩展。

Answer 1

在第二项上执行二项式展开：

T(n) = T(n^(1/2)) + T(n-n^(1/2)) + n

之所以可以这样做是因为，对于大的1/q < 1值，其反过来又意味着n^(1/q-1) << 1。

代入重复：

n

[因为1 - 2/q > 0，所以对于q > 2的较大值，第三项会快速衰减，这意味着可以在渐近极限中忽略它：

n

使用类似的技术，下一个扩展将是：

因此：

---

一些数值测试结果：

对于

q   | 3       4         5         6         7         8         9         10
m   |                                 T(10^m, q)
------------------------------------------------------------------------------------
1   | 8       10        10        10        10        10        10        10
2   | 38      54        65        81        100       100       100       100
3   | 164     272       389       486       563       627       755       1000
4   | 728     1447      2222      2994      3761      4554      5255      5511
5   | 3300    7835      13471     19497     25699     31681     36869     43686
6   | 15149   43199     82438     128804    177495    226212    275381    343686
7   | 69946   240337    511496    854128    1249628   1648028   2123037   2586014
8   | 323861  1343497   3193858   5735972   8792779   12228031  15705474  19268220
9   | 1501499 7529750   20024691  38712540  62366319  89586305  120308456 152184297
10  | 6965614 42264115  125845996 262058267 444972781 664753359 914166923 1188039787

的所有值，T(n)对n的对数-对数图：

q

线性对数-对数图对应于多项式关系，这与的理论结果一致。指数由梯度的值给出：

n^(1-1/q)

梯度与理论值相当吻合，但偏低。这可能是由于用于数字测试的代码中的整数截断所致。