T(n)= T(n/10)+ T(an)+ n，如何解决? [英] T(n) = T(n/10) + T(an) + n, how to solve this?

问题描述

更新:我仍在寻找一种解决方案，而无需使用外部资源.

给出::对于某些 a ， T(n)= T(n/10)+ T(an)+ n :如果 n< T(n)= 1 10 ，我想检查以下内容是否可能(对于某些 a 值，我想找到最小的 a ):

Given: T(n) = T(n/10) + T(an) + n for some a, and that: T(n) = 1 if n < 10, I want to check if the following is possible (for some a values, and I want to find the smallest possible a):

对于每个 c>0 中有 n 0 >0 ，这样对于每个 n>n 0 ， T(n)> = c * n

For every c > 0 there is n0 > 0 such that for every n > n0, T(n) >= c * n

我试图一步一步地打开函数声明，但是它真的很复杂，因为我根本看不到进步，所以被卡住了.

I tried to open the function declaration step by step but it got really complicated and I got stuck since I see no advancement at all.

这就是我所做的:(很抱歉添加图像，因为我在单词上写了很多，不能将其粘贴为文本)

Here is what I did: (Sorry for adding an image, that's because I wrote a lot on word and I cant paste it as text)

请帮忙吗?

推荐答案

调用Akra–Bazzi ，g(n)=n¹，因此临界指数为p = 1，因此我们希望(1/10)¹+a¹= 1，因此a = 9/10.

Invoking Akra–Bazzi, g(n) = n¹, so the critical exponent is p = 1, so we want (1/10)¹ + a¹ = 1, hence a = 9/10.

直觉上，这就像mergesort重复发生:在每次调用时都有线性开销，如果我们不减小子问题的总大小，我们将在运行时间上得到一个额外的日志(它将超过任何时间)常数c).

Intuitively, this is like the mergesort recurrence: with linear overhead at each call, if we don't reduce the total size of the subproblems, we'll end up with an extra log in the running time (which will overtake any constant c).

这篇关于T(n)= T(n/10)+ T(an)+ n，如何解决?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！