减法在大 O 符号中有效吗？
Subtraction is valid in big O-notation?
如果我们有f(n)=O(g(n))和h(n)=O(x(n))，那么f(n)-h(n)=O(g(n)-x(n))是真的吗？
我不这么认为，因为从 g(n) 中减去 x(n) 时，O 表示法定义中的不等式会被反转，也就是说；因为 f(n)<=c_1g(n) 对于某个常量 c_1 和 h(n)<=c_2x(n) 对于另一个常量 c_2，不清楚我们是否可以直接减去这些项。有什么提示吗？提前致谢。
你是对的。 f(n) 是 O(g(n)) 和 h(n) 是 O(x(n)) 并不意味着 f(n)-h(n) 是 O(g(n)-x(n)).
作为反例，只需取 g(n) = x(n) = 1 和 f(n) = 2 以及 h(n) = 1。这显然满足假设，但是 f(n)-h(n) = 1，而 g(n)-x(n) = 0 等说法不成立。
关于区别，您唯一可以说的是 O(max(|h(n)|, |x(n)|))。
但是请注意，如果函数允许负值，则加法也是如此。在与编程相关的上下文中，通常假设该函数只取正值，在这种情况下减法只有部分意义。
如果我们有f(n)=O(g(n))和h(n)=O(x(n))，那么f(n)-h(n)=O(g(n)-x(n))是真的吗？
我不这么认为，因为从 g(n) 中减去 x(n) 时，O 表示法定义中的不等式会被反转，也就是说；因为 f(n)<=c_1g(n) 对于某个常量 c_1 和 h(n)<=c_2x(n) 对于另一个常量 c_2，不清楚我们是否可以直接减去这些项。有什么提示吗？提前致谢。
你是对的。 f(n) 是 O(g(n)) 和 h(n) 是 O(x(n)) 并不意味着 f(n)-h(n) 是 O(g(n)-x(n)).
作为反例，只需取 g(n) = x(n) = 1 和 f(n) = 2 以及 h(n) = 1。这显然满足假设，但是 f(n)-h(n) = 1，而 g(n)-x(n) = 0 等说法不成立。
关于区别，您唯一可以说的是 O(max(|h(n)|, |x(n)|))。
但是请注意，如果函数允许负值，则加法也是如此。在与编程相关的上下文中，通常假设该函数只取正值，在这种情况下减法只有部分意义。