algorithm - 大 O 符号 : "n" is "O(0.5n)"?

Question

定义:

例子:

f(n) = n

g(n) = 0.5n

请注意，当 c = 1 且 n0 = 1 时，对于所有 n >= n0，n >= 1(0.5n)。

但是，定义指出“存在”一个实常数 c > 0，而不是“对所有”。所以在这种情况下，如果我们选择 c = 3 和 n0 = 1，则 n <= 3(0.5n) 对于所有 n >= n0 成立，因此，n 是 O(0.5n )?

如果是这样，n is O(0.5n) 语句的语义是什么？
n对无穷大的行为类似于0.5n的行为？

Answer 1

是的，0.5n 也是 O(n)。对于 Big-O，您始终可以删除常量(阅读:忽略常量)，因为它们不会随着输入大小而增长。

编辑:刚看到您的编辑。 Big-O 的语义意义不是一个函数在任意输入大小下与另一个函数“表现相似”——而是一个函数在常数因子内被另一个函数上限。

另请参阅此帖子的第二个答案:What is a plain English explanation of "Big O" notation?