math - 大哦符号（如何写一个句子）

Question

我有一个关于渐近符号的测试，有一个问题：

考虑以下：

O(o(f(n)) = o(f(n))

1. 使用渐近符号的约定，用文字写出陈述的含义。
2. 陈述是真的还是假的？证明合法。

我弄错了（不完全记得我写了什么），但我认为是这样的：

对于任何函数 g(n) = o(f(n))，都有一个函数 h(n) = o(f(n))，因此 h(n) = O(f(n))。

这是对的吗？

对于（2），我不完全确定。有人可以帮我解决这个问题吗？

提前致谢。

Answer 1

我认为他们试图问一个关于大 O 和小 o 渐近符号之间关系的问题。

A) 小 O 有界函数的大 O 边界简化为/实现该函数的小 O 边界。

B) 是的。Big O 是一个不太“严格”的界限，因为它规定存在一个 M 和一个 x0，使得 f(n) <= M * g(n) for x >= x0，而 Little O 规定对于所有正 M ，有一个 x0 使得 f(n) 的上限为 M * g(n)。

因此，大 O 的“一个 M”是小 O 的“所有 M”的子集，因此 O(o(f(n)) 等价于 o(f(n))。

对于实际的数学而不是我的弱 ascii，请参阅维基百科页面

Answer 2

简单的英语含义：严格大于 f(n) 的函数的上限严格大于 f(n) 您的语句可以写成：对于任何函数 g(n)=o(f(n) ) 存在 h(n)=O(g(n)) 这意味着 h(n) 也是 o(f(n)) => O(g(n)) = o(f(n)) => O (o(f(n))) = o(f(n)) 是的，这个陈述是正确的。（当然，上面的陈述假设所有正确的常数和使用“严格更大是可读性和理解性：它应该是“严格的上限”）

Answer 3

对不起，如果这看起来有点旁白，但我认为这是一个狡猾的问题（正如 Alexandre C 所暗示的那样），因为它是对符号的相当大的滥用。

通常教授大 O 表示法的方式（尤其是在计算机科学课上）就像 O(f(n)) 是一个函数。这应该引起一些警钟，因为陈述“n = O(n)”和“2n = O(n)”都是正确的，但“n = 2n”不是。如果我们想说“f(n) 是 g(n) 的大 O”，我们在技术上不应该说“f(n) = O(g(n))”，而是应该说“f(n )是O(g(n))" 的一个元素。前者只是一种方便的简写。

所以回到实际的问题，O(o(f(n))) 并不真正意味着很多（或者至少我从未见过一组函数的 big-O 的正式定义）。但我想解释它的合乎逻辑的方式是按照 enjay 的回答，g(n) = o(f(n))。