定义:
例子:
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的行为？
最佳答案
是的，0.5n 也是 O(n)。对于 Big-O，您始终可以删除常量(阅读:忽略常量)，因为它们不会随着输入大小而增长。
编辑:刚看到您的编辑。 Big-O 的语义意义不是一个函数在任意输入大小下与另一个函数“表现相似”——而是一个函数在常数因子内被另一个函数上限。
另请参阅此帖子的第二个答案:What is a plain English explanation of "Big O" notation?
关于algorithm - 大 O 符号 : "n" is "O(0.5n)"?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46258160/