几何级数平方和的复杂性
提问于 2018-06-26 06:31:24
我在数据结构课程的作业中有一个问题，我想出了两个算法来解决这个问题，一个是O(n^2)时间，另一个是：
T(n) =3*n+ 1*1 + 2*2 + 4*4 + 8*8 + 16*16 +.+ logn*logn
我不确定哪一个更好。
我知道，从1到logn的几何级数之和是O(logn)，因为我可以使用几何级数公式。但是这里有几何级数的平方，我不知道如何计算。
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-06-26 07:37:10
您可以将其改写为：
log n * log n + ((log n) / 2) * ((log n) / 2) + ((log n) / 4) * ((log n) / 4) ... + 1如果您用log^2 n代替(更容易理解) x，您将得到：
x + x/4 + x/16 + x/64 + ... + 1你可以用公式来和这个系列，但是如果你不必是正式的，那么基本的逻辑就足够了。假设你有1/4的馅饼，然后再加上1/16和1/64等等，你就能清楚地看到，它永远不会达到整块，因此：
x + x/4 + x/16 + x/64 + ... + 1 < 2x意味着它的O(x)
将x改为log^2 n
T(n) = O(3*n + log^2 n) = O(n)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51045413
复制
腾讯云开发者
