0

我一直试图找到一个解决方案，其中 0 < k_1*c^n <= b^n <= k_2*c^n，但到目前为止我还没有运气。根据我对关于时间复杂度的维基百科文章的理解，所有形式 a^n 的函数都应该具有相同的渐近增长。这是假的吗？

4

1 回答 1

3

错误的。为简单起见，假设b = 2*a. b^n是2^n*a^n。对于任何常数c，都存在n这样2^n > c，所以b^n > c * a^n。

不可能找到常数 m 和 c 使得对所有都不n>m, b^n <= c*a^n是。b^nO(a^n)

于 2013-09-14T23:05:43.627 回答