该算法的计算复杂度

考虑 $n,k\in\mathbb{N}$ 的函数 $f(n,k)$ 以及应用该函数的算法。 该算法的框架如下:

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

这个算法的计算复杂度是多少? 具体来说,是 $O(n)$ 还是 $O(2^n)$?

0
2022-06-07 14:40:35
资源 分享
答案: 1

@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

我们注意到,如果 f (n, k) 是 (n),之后它会另外是 (2 ^ n) ; 然而,在这种情况下,它不是 (n) 考虑到(如@Listing 提到的)k' 可以得到比 n 更多的值,考虑到 k' 处理所有值多达 2 ^ n - 1 (例如,当 k = 2 ^ n - 1,k' = 2 ^ n - 1),以及|2 ^ n - 1|>|n|对于所有常数 A,因为 n 趋于无穷大。

有关大 O 表示法的更多信息,请参见 这一页

1
2022-06-07 15:08:46
资源