# 该算法的计算复杂度

• 做一些需要 $O(n)$ 时间的估计
• 指定 $k' = k \mod 2^n$
• 做一些需要 $O(k')$ 时间的计算

0
2022-06-07 14:40:35

@Listing 是对的。

f(n,k)
= *O*(n) + *O*(1) + *O*(k')
= *O*(n) + *O*(1) + *O*(2^n)
= *O*(2^n)


|f(n,k)|
<= M|n| + C|1| + N|k'| as x goes to infinity, and some constant M and N that satisfy:
(a) |work in part one| <= M|n|
(b) |definition of part two| <= C|1| (by assumption)
(c) |work in part three| <= N|k'|
as given or assumed.

<= M|n| + C|1| + N|2^n| since |k'| <= 1|2^n| as x goes to infinity (all k' are bounded above by 2^n by the definition of mod)

<= N|2^n| since | M|n| + C|1| + N|2^n| | <= 2N|2^n| as x goes to infinity


1
2022-06-07 15:08:46