有没有一种通用的方法来计算带步长的循环的渐近时间复杂度？

Question

有没有一种通用的方法/方法论来计算这类循环的渐近时间复杂度？

j=a
while j<n do
    j=f(j)

其中f(j)可以是j+1，2*j，j*j等。

请注意，上面的代码等同于C for循环。

for (j=a; j<n; j=f(j));

- Da Mike

---

一般的方式是要“知道”f是什么。 - user3235832

Answer 1

首先是答案，然后是一般的方法：

1）如果 f(j) = j + 1，则您大约需要 n 步才能到达 n。

2）如果 f(j) = 2*j，则每次都是将其加倍，所以大约在 log n 步后到达 n。

3）如果 f(j) = j*j，则它将是 a、a^2、a^4、a^8 等等；因此，大约在 loglog n 步后到达 n。

那么，一般的方法是什么呢？您找到模式并将其等于 n，然后解方程：

1）应用 f x 次将给出 a + x，因此 a + x = n，因此 x = n - a = O(n)。

2）应用 f x 次将给出 a*(2^x)，因此 a*(2^x) = n，因此 x = log n/a = O(log n)。

3）应用 f x 次将给出 a^(2^x)，因此 a^(2^x) = n，因此 2^x = log_a n，因此 x = log log_a n = O(log log n)。（log_a n 是以 a 为底的对数）

希望这有所帮助。

- A. Mashreghi

Answer 2

这种方法是通过解决递归式来实现的。

F(j+1) = f(F(j)), F(0) = a.

然后解决不等式。

F(k(n)) < n <= F(k(n)+1), 

对于 k(n)，其复杂度为 O(k(n))。

例如，f(j):= j² 会产生以下结果：

F(j+1) = F²(j), F(0)= a

其中包含解决方案

F(j) = a^(2^j).

然后通过反转

k(n) ~ log(log(n)/log(a))/log(2) = O(log(log(n))).

- user1196549

---

嗯.. F函数的意义是什么？J如何成为n的一个函数？你能再解释一下吗？ - Da Mike

F 是 f(a) 的第 j 次迭代。为了更好的严谨性，我将更改关于 j 的符号表示。 - user1196549