标签 algorithm
<分区>
我正在寻求有关如何确定特定函数边界的说明。
例如 1:A(n) = log(2^n) + n^(1/3) + 1000 我是否可以说最后两个术语可以“忽略”，因为它们与第一个相比微不足道？因此边界是 O(2^n)？
例如 2:B(n) = n + (1/2)*n + (1/3)*n + (1/4)*n + ... + 1 我对这个比较不确定，但我猜它会是 O(n)？ 1 被忽略(根据例如 1 中 1000 的推理)，这就是我确定的。
也在考虑 E.g. 中的分数是否2 被修改，使得分母以不同的模式运行(例如(1/2)* n +(1/4)* n)+(1/8)* n ...)，增长的顺序是比 E.g. 更快/更慢2?
感谢任何可用的指导!谢谢!
最佳答案
E.g 1: A(n) = log(2^n) + n^(1/3) + 1000
这里 log(2^n) = n 大于 n^(1/3) 所以根据 Order 函数的性质 A(n0 = O(n)
E.g 2: B(n) = n + (1/2)*n + (1/3)*n + (1/4)*n + ... 1
= n*(1 + 1/2 + 1/3 + 1/4 ....+ 1/n)
现在 (1 + 1/2 + 1/3 + 1/4 ....) 你可以近似认为它是 dx/x 从 1 到 n 的积分，它变成 log(n) 使得结果顺序 = O(nlgn)
E.g 2 Modified = n + (1/2)*n + (1/4)*n + (1/8)*n +.....
= n( 1+ 1/2 + 1/4 +1/8...) [GP series]
= n / (1/(1-1/2))
= 2n
所以就变成了O(n)
关于algorithm - 成长顺序分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48484619/