T（n）= 4 T（n/3）+ lg n

-1

我该如何解决这个复原关系？ T（n）= 4T（n/3）+ lg n我知道主定理 - 案例1适用，但我不明白为什么。我到现在为止的方式就是这个。 a = 4，b = 3，f（n）= lg n。T（n）= 4 T（n/3）+ lg n

是lg n =（lg10 n）还是（lg2 n），我知道由于（lge n）这并不重要，但我仍然不明白为什么它不重要，如果它是lg10或lg2 。我可以计算（lg10 n）/（lg2 n）或某物。出于某种原因，这并不重要，但为什么？...但让我们继续。

n^log3^4〜1.26但是在n^someting方面什么是lg n。

另一个例子，所以也许你理解我。如果我有f（n）= n的平方根，而不是lg n，它将是f（n）= n^0.5。当e> 0时，对于e = 1，第一种情况，f（n）变为n^logb ^（ae）= n^log3 ^（4-1）= n的元素。^log3中^ 3。 n^1是n^0.5元素吗？是？因为它更小？，所以这导致n^logb^a或T（N）= O（N^logba）或O（n^log3^4）。

如果这是正确的我如何遵循这种方式f（n）= lg n？

我希望你明白我的问题，我不能正确格式化所有n^logba的东西。

来源

2015-05-03 Matthias Köhler

这是一个编程相关问题的网站，所以不幸的数学问题在这里是题外话题，但你可能会在[数学堆栈交换]（http://math.stackexchange.com/）上得到帮助。 – Frxstrem

我投票结束这个问题作为题外话，因为它不是一个编程问题。它可能属于http://math.stackexchange.com/ –

否。对数函数的增长率小于指数大于0的任何多项式函数。也就是说，即使像x^0.0000001之类的东西最终也会比log x增长得更快。

所以在这种情况下它的O（n^log_3 4）。

来源

2015-05-03 23:56:07

T（n）= 4 T（n/3）+ lg n

回答

相关问题