3

我正在寻找一个简单的示例函数 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))。我们在课堂上了解到 little-o 符号的一个定义是 f(n)/g(n) as n --> infinity 是否为 0。在这种情况下，f(n)/g(n) as n到无穷大接近 1，因此 f(n)不是o(g(n))。

这个逻辑正确吗？我错过了什么吗？

4

1 回答 1

3

是的，你的推理是正确的，你的结论是正确的。

对此的另一种思考方式是，O(g)函数集的渐近增长速度不比 快g，而o(g)函数集的渐近增长速度慢于g。所以如果f以与 相同的渐近率增长g，则f在O(g)而不是o(g)。集合o(g)是 的子集O(g)，和集合的差O(g) \ o(g) = Θ(g)。

作为一个学究，我不得不注意到你要求一个“函数，f(n)，即其他函数的 Big-O，g(n)”（强调我的），所以你应该选择一个不同的函数喜欢g(n) = 2n它是其他一些功能。;-)

于 2020-02-06T04:34:52.413 回答