检查复杂度（Big O表示法）

Question

在面试时我有一个问题：是不是真的40^n是O(2^n)我是说，因为只有指数计数和不断无所谓。然后我想知道是否(40n)^2是O(n^2)，在这里我感觉不对，这不是因为下一个的差异n很大，但是无法正式证明这一点。这两个毫无疑问的答案是什么？

Answer 1

40 ^ n是O（2 ^ n）是真的吗，我说是，因为只有指数计数和常数无关紧要。

这是一个很大的捷径，在这里不起作用。为了使40 ^ n处于O（2 ^ n）中，必须有一对常数c和n ₀，如果n> = n ₀，则40 ^ n <= c * 2 ^ n 。但是没有。如果尝试解决c的问题，结果c必须为20 ^ n，这不是常数。像这样的指数基不能被忽略。

然后我问（40n）^ 2是否为O（n ^ 2）

如果算出平方，您将得到1600 n ^ 2。现在有是一个解决方案，使得C和N ₀是常数，例如，C = 1600，N ₀ = 1所以，是（40N）^ 2为O的元素（N ^ 2）。