有没有一种通用的方法/方法论来计算这类循环的渐近时间复杂度?
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));
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));
首先是答案,然后是一般的方法:
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 为底的对数)
希望这有所帮助。
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))).
F
是 f(a)
的第 j
次迭代。为了更好的严谨性,我将更改关于 j
的符号表示。 - user1196549
f
是什么。 - user3235832