algorithm - 什么是以下时间复杂度？

Question

如果一个for循环被定义为 for (int i = 2; i < n; i = i*i + i) “i*2+i”代表什么时间复杂度。big-O 表示法中的时间复杂度是多少？我如何解决这个不断增加的索引的大 O 表示法？例如： i = 2 , 6 , 42 , 1086 , ....（通式“i*2+i”）

标签： algorithmfor-loopindexingtimetime-complexity

Answer 1

由于i具有具体类型 ( int)，它是有界的，复杂性是 perforce O(1)。

此外，该功能的增长速度如此之快，以至于int到第六学期就超过了an的容量。

---

如果认为给定代码是伪代码并且ints 是无界的，那么可以使用

i[k]² <= i[k+1] = i[k]² + i[k] <= a i[k]²

其中a是一个待确定的常数。

然后取以 2 为底的对数

2 lg i[k] <= lg(i[k+1]) <= 2 lg(i[k]) + lg(a)

并通过归纳

2^m lg(i[k]) <= lg(i[k+m]) <= 2^m lg(i[k]) + (2^m - 1) lg(a) <= 2^m lg(a.i[k])

再次取对数，

m + lg(lg(i[k])) <= lg(lg(i[k+m])) <= m + lg(lg(a.i[k]))

也写了

lg(lg(i[k+m])) - lg(lg(a.i[k])) <= m <= lg(lg(i[k+m])) - lg(lg(i[k]))

Asm表示第一次之后的迭代次数k，因为n = i[k + m]我们有

lg(lg(n)) - lg(lg(a.i[k])) <= m <= lg(lg(n)) - lg(lg(i[k]))

特别是，有了k=0，我们可以取a = 3/2和

lg(lg(n)) - lg(lg(3)) <= m <= lg(lg(n)) - lg(lg(2))

这证明m = Θ(lg(lg(n))。