首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >求解T(n)= 9T(n / 10)+ log ^ 3 n?

求解T(n)= 9T(n / 10)+ log ^ 3 n?
EN

Stack Overflow用户
提问于 2019-06-03 00:27:34
回答 2查看 0关注 0票数 0

我有复发

T(n)= 9T(n / 10)+ log 3 n

而我正试图找到它的复杂性。

在i-substitution之后,我可以看到

T(i)= 9T(n / 10 i + 1)+ log 3(n / 10 i)。

但是,我不知道如何继续。我该如何解决这种复发?

EN

回答 2

Stack Overflow用户

发布于 2019-06-03 09:27:31

有时用于解决这类复发的技术是通过两次更简单的复发来重复上限和下限,并查看您找到的内容。

例如,请注意您的重复发生

T(n)= 9T(n / 10)+ log 3 n

复发率较低

L(n)= 9L(n / 10)+ 1。

这种重现可以使用主定理直接求解。主定理有许多不同的表述,但我最喜欢的是解决表格复发的问题

T(n)= aT(n / b)+ n d

对于常数a,b和d。在这种情况下,我们有a = 9,b = 10,并且d = 0,并且由于log b a> d,这意味着递推求解为L(n)=Θ(n log 10 9)。这意味着我们知道您的重现率至少为Ω(n log 10 9)。

同样,请注意您的重现是由上限限定的

U(n)= 9U(n / 10)+ nε

对于任何固定的ε> 0,因为任何多项式项都支配对数项的任何常数幂。让我们假设ε非常非常小。在这种情况下,主定理说了什么?这里,我们有a = 9,b = 10,并且d =ε。假设ε确实非常非常小,我们将log b a>ε,因此递推求解为Θ(n log 10 9)。

这表明你的重现很好地夹在两个其他的重现之间,分别是Ω(n log 10 9)和O(n log 10 9),所以你的重复解释为Θ(n log 10 9)

总结一下:

  • 如果您添加了一个不常见的函数术语,您有时可以通过使用更简单的附加项重复出现的上限和下限来解决该重现。
  • 对数由常数下限,并由任何(正,恒定功率)多项式上限。

希望这可以帮助!

票数 0
EN

Stack Overflow用户

发布于 2019-06-03 09:57:05

使用master方法来解决问题

它解决了形式T(n)= aT(n / b)+ f(n)的重现。

Master Method是获得解决方案的直接方式。主方法仅适用于以下类型的重复或可转换为后续类型的重复。

T(n)= aT(n / b)+ f(n)其中a> = 1且b> 1有以下三种情况:1。如果f(n)=Θ(nc)其中c <Logba则为T( n)=Θ(nLogba)

  1. 如果f(n)=Θ(nc)其中c = Logba则T(n)=Θ(ncLog n)

3.如果f(n)=Θ(nc)其中c> Logba则T(n)=Θ(f(n))

.it用于解决函数的复发,如T(n)= aT(n / b)+ f(n)其中a> = 1且b> 1与您的相同

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/-100009070

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档