Big Oh 符号（如何写一个句子）
我对渐近符号进行了测试，有一个问题：
考虑以下内容：
O(o(f(n)) = o(f(n))
- 使用渐近符号的约定，用文字写出该语句的含义。
- 该语句是真还是假？请证明。
我错了（不完全是这样）记住我写的），但我认为是这样的：
对于任意函数 g(n) = o(f(n))，有 是一个函数 h(n) = o(f(n)) 使得 h(n) = O(f(n))。
正确吗？
对于（2），我不完全确定。有人也可以帮我解决这个问题吗？
提前致谢。
I had a test about asymptotic notations and there was a question:
Consider the following:
O(o(f(n)) = o(f(n))
- Write in words the meaning of the statement, using conventions from asymptotic notation.
- Is the statement true or false? Justify.
I got it wrong (don't exactly remember what I wrote), but I think is something like:
For any function g(n) = o(f(n)), there
is a function h(n) = o(f(n)) so that
h(n) = O(f(n)).
Is it correct?
And for (2), I'm not totally sure. Can someone help me with this one too?
Thanks in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我认为他们试图提出一个关于大 O 和小 O 渐近符号之间关系的问题。
A) 小 O 有界函数的大 O 界简化为/实现该函数的小 O 界。
B）正确。大 O 是一个不太“严格”的界限，因为它规定存在一个 M 和一个 x0，使得 f(n) <= M * g(n) 对于 x >= x0，而小 O 规定对于所有正 M，存在 x0 使得 f(n) 的上限为 M * g(n)。
因此，大 O 的“一个 M”是小 O 的“所有 M”的子集，因此 O(o(f(n)) 等价于 o(f(n))。
对于实际数学而不是我的 ascii 弱，请参阅 wikipedia 页面
I think they were trying to ask a question about the relationship between Big O and little o asymptotic notation.
A) Big O bounding of a Little O bounded function reduces to/imples the Little O bound of that function.
B) True. Big O is a less "strict" bound in that it stipulates that there is an M and an x0 such that f(n) <= M * g(n) for x >= x0, whereas Little O stipulates that for all positive M, there is an x0 such that f(n) is upper-bounded by M * g(n).
Thus the "an M" of Big O is a subset of the "all M" of little O, and so O(o(f(n)) is equivalent to o(f(n)).
For the actual math and not my weak ascii, see the wikipedia page
用简单的英语表达的意思：
严格大于 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))
是的，这个说法是正确的。
（当然，上述陈述假设所有正确的常量，并使用“严格更大是 fr 的可读性和理解性：它应该是“严格的上限”）
Meaning in plain English :
The upper bound of a function that is strictly greater than f(n) is strictly greater than f(n)
Your statement could have been written as : For any function g(n)=o(f(n)) there exists h(n)=O(g(n)) which implies h(n) is also o(f(n)) => O(g(n)) = o(f(n)) => O(o(f(n))) = o(f(n))
Yes the statement is correct.
(of course the above statement assumes all the correct constants and the use of "strictly greater is fr readability and understanding : it should be "a strict upperbound")
抱歉，如果这看起来有点旁白，但我认为这是一个狡猾的问题（正如 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))) 并不真正意味着很多（或者至少我从未见过一组函数的大 O 的正式定义）。但我想解释它的逻辑方法是按照enjay的答案，g(n) = o(f(n))。
Sorry if this seems like a bit of an aside, but I think it's a dodgy question (as Alexandre C has alluded to) as it's a pretty big abuse of notation.
The way big-O notation is commonly taught (especially in a computer science class) is as if O(f(n)) is a function. This should set off some alarm bells, as the statements "n = O(n)" and "2n = O(n)" are both true, but "n = 2n" is not. If we want to say "f(n) is big-O of g(n)" we technically shouldn't be saying "f(n) = O(g(n))", rather we should say "f(n) is an element of O(g(n))". The former is just a convenient shorthand.
So back to the actual question, O(o(f(n))) doesn't really mean a whole lot (or at least I've never seen a formal definition of big-O of a set of functions). But I guess the logical way to interpret it would be as per enjay's answer, with g(n) = o(f(n)).