在 Big-O 中起作用，但在 Little-O 中不起作用
Function in Big-O, but not in Little-O
我正在寻找一个简单的示例函数 f(n)，它是其他函数 g(n) 的 Big-O，但不是 g(n) 的 Little-o。换句话说，一些 f(n) 使得 f(n) 是 O(g(n))，而不是 o(g(n))。
我能想到的最简单的情况是f(n) = n, g(n) = n。 f(n) 显然是 O(g(n))。我们在 class 中了解到，little-o 表示法的一个定义是 f(n)/g(n) 是否随着 n --> 无穷大，变为 0。在这种情况下，f(n)/g(n ) 随着 n 趋于无穷大接近 1，因此 f(n) 是 而不是 o(g(n))。
这个逻辑对吗？我错过了什么吗？
是的，你的推理是正确的，你的结论是正确的。
另一种思考方式是 O(g) 是渐近增长不比 g 快的函数集，而 o(g) 是增长渐近的函数集渐近地慢于 g。因此，如果 f 以与 g 相同的渐近速率增长，则 f 在 O(g) 而不是 o(g)。集合o(g)是O(g)的子集，集合差O(g) \ o(g) = Θ(g).
作为一个书呆子，我不得不注意到你要求一个 "function, f(n), that is Big-O of some other function, g(n)"（强调我的），所以你应该选择一个不同的函数，比如 g(n) = 2n 因为它是一些 other 函数。 ;-)
我正在寻找一个简单的示例函数 f(n)，它是其他函数 g(n) 的 Big-O，但不是 g(n) 的 Little-o。换句话说，一些 f(n) 使得 f(n) 是 O(g(n))，而不是 o(g(n))。
我能想到的最简单的情况是f(n) = n, g(n) = n。 f(n) 显然是 O(g(n))。我们在 class 中了解到，little-o 表示法的一个定义是 f(n)/g(n) 是否随着 n --> 无穷大，变为 0。在这种情况下，f(n)/g(n ) 随着 n 趋于无穷大接近 1，因此 f(n) 是 而不是 o(g(n))。
这个逻辑对吗？我错过了什么吗？
是的，你的推理是正确的，你的结论是正确的。
另一种思考方式是 O(g) 是渐近增长不比 g 快的函数集，而 o(g) 是增长渐近的函数集渐近地慢于 g。因此，如果 f 以与 g 相同的渐近速率增长，则 f 在 O(g) 而不是 o(g)。集合o(g)是O(g)的子集，集合差O(g) \ o(g) = Θ(g).
作为一个书呆子，我不得不注意到你要求一个 "function, f(n), that is Big-O of some other function, g(n)"（强调我的），所以你应该选择一个不同的函数，比如 g(n) = 2n 因为它是一些 other 函数。 ;-)