2 ^ n和2 ^（n / 2）之间的渐近增长关系

Question

我正在解决这个问题f(n) = 2^ng(n) = 2^(n/2)f(n) = ?(g(n))我找到了许多答案，分别是Ω和ω。但是不是f(n) = θ(g(n))吗？既然常量不应该影响函数的增长？

Answer 1

f(n) = θ(g(n))当且仅当f(n) = Ω(g(n))和f(n) = O(g(n))时，但是我们可以看到f(n) = O(g(n))并不成立，如下所述。

O（g（n））= {f（n）：存在正常数c和n0，使得0 <= f（n）<= c g（n）对于所有n> = n0}

2 ^ n <= c 2 ^（n / 2）将导致2 ^（n / 2）<= c，我们找不到这样的n0来使上面的定义成立。

n = np.linspace(1, 10)
plt.plot(n, 2 ** n, label="2 ** n")
plt.plot(n, 2 ** (n/2), label="2 ** (n/2)")
plt.legend(loc='upper left')
plt.show()

参考：CLRS