gpt4 book ai didi

big-o - 在 Big-O 中起作用,但在 Little-O 中不起作用

转载 作者:行者123 更新时间:2023-12-01 13:10:52 25 4
gpt4 key购买 nike

我正在寻找一个简单的示例函数 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) 作为 n --> 无穷大,是否为 0。在这种情况下,f(n)/g(n) 作为 n到无穷大接近 1,因此 f(n) 是 不是 o(g(n))。

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

最佳答案

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

另一种思考方式是O(g)是不比g渐进增长更快的函数集, 和 o(g)是渐近增长慢于 g 的函数集.所以如果 f以与 g 相同的渐近率增长,然后 fO(g)但不是 o(g) .套装o(g)O(g) 的子集,和集差O(g) \ o(g) = Θ(g) .

作为学究,我不得不指出您要求“函数,f(n),即某些 其他 函数的 Big-O,g(n)”(重点是我的),所以你应该选择一个不同的函数,比如 g(n) = 2n因为它是一些 其他 功能。 ;-)

关于big-o - 在 Big-O 中起作用,但在 Little-O 中不起作用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60087743/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com