time-complexity - Big O 表示法中 g(n) 的值

Question

根据大 O 表示法的定义，令 g 和 f 是从自然数集到自身的函数。如果存在常数 c 和自然 n 0 使得 f (n) ≤ cg(n) 对于所有 n > n0 ，则函数 f 被称为 O(g)。那么，如果 f(n) = O(n)，我们可以说 g(n) = n 吗？

标签： time-complexitybig-o

Answer 1

首先，你的问题没有很好的定义。从表面上看这个问题，答案是否定的：给定f ∈ O(n)，当然我们不能这么说，g(n) = n因为您在假设的前提中没有提到g。您只g在 的定义中提到O，但定义与您的假设之​​间没有联系。

所以也许你的意思是：给定f ∈ O(n)和f ∈ O(g(n))，它是否遵循g(n) = n？答案显然是否定的。

所以也许你的问题更多的是关于符号：写作O(n)等同于写作O(g)whereg(n) = n吗？这是一个更有趣的问题，我将尝试更详细地回答。

首先请注意，O-notation 的使用方式在各个方面都很草率，这可能会导致一些混乱。最明显的草率来自人们经常写f = O(g)的意思f ∈ O(g)。您的情况的混淆可能至少部分是由于不太经常注意到的马虎。

通常被掩盖的是有无数不同的 O 运算符：

1. O 运算符将函数作为参数。在这种情况下，O 运算符（隐式）由函数的数量参数化。为了明确这一点，我们可以写O_1(g)whereg(x) = x或O_2(f)where f(x,y) = x。请注意，在此示例中，O_1(g)并且O_2(f)不表示相同的集合，即使函数体都是x.

2. O 运算符将函数体作为参数。在这种情况下，O 运算符（隐式）由变量名称的有序序列参数化，并以类似于 lambda 绑定的方式起作用。为了明确这一点，我们可以写O_n(n)or O_{n,m}(n)。再次注意，这两者不相等。然而，这些等式成立：O_n(n) = O_1(g)和O_{n,m}(n) = O_2(f)。另请注意，变量名称可以字母重命名，因此O_n(n) = O_x(x) = O_y(y).

（通常没有人明确说明这些参数。但了解隐含的情况会有所帮助。例如，当人们说“复杂性不是O(E)但O(V)”之类的话时，他们隐含地，也许在不知不觉中，使用了二元O-运算符O_{E,V}，否则该语句将毫无意义，因为O_E(E) = O_V(V)！）

所以回到你的问题：如果你写O(n)，那么你可能是说O_n(n)，如果你写O(g)，你可能是说O_1(g)。如果是这样，那么两者确实是相等的。但请注意，这O_n(n)也等于例如O_1(h)where h(x) = 2x + 1。

希望你现在不会更加困惑！