大O证明与开方和日志

我无法搞清楚如何证明大O证明与开方和日志

t(n) = sqrt(31n + 12n log n + 57)

是

O(sqrt(n) log n)

我还没有过尚未处理平方根在大O符号所以我遇到了很多麻烦！任何帮助非常感谢:)

来源

2011-02-24 deedex11

这是功课吗？如果是这样，请添加该标签。 – 2011-02-24 19:50:45

不做功课！只是练习，所以我不认为这个标签是必要的，但谢谢！ – deedex11 2011-02-24 20:39:31

大O符号是关于算法特征（时间花费的时间，内存使用，处理时间）如何随问题的大小而增长。

常量因素被丢弃，因为它们不会影响值的大小。

小项也被丢弃，因为它们最终没有效果。

所以你的原方程

sqrt(31n + 12nlogn + 57)

立即简化为

sqrt(n log n)

平方根分布，象其他类型的乘法和除法，所以这可以被straightforwardedly转换为：

sqrt(n) sqrt(log n)

由于日志将乘法转换为加法（this所以计算尺工作），这将成为：

sqrt(n) log (n/2)

同样，我们抛弃常量，因为我们感兴趣的类的行为

sqrt(n) log n

和，我们找到了答案。

更新

正如已经正确地指出，

sqrt(n) sqrt(log n)

不会成为

sqrt(n) log (n/2)

所以我推导的最终是错误的。

来源

2011-02-24 19:57:54 Bevan

sqrt（log n）不是log（n/2）。 – 2011-02-24 20:00:18

@克里斯达恩。你是对的。让我的业务逆转。经典案例，看看我想要什么，最终在预定义点。谢谢你的收获。 – Bevan 2011-02-24 20:06:25

不用担心。我认为它是一个* big * O，所以我们不必为最后一点而努力...... sqrt（log n）明显小于log n最终:) – 2011-02-24 20:30:32

首先找到sqrt()，这将是12nlogn内最大程度的因素。最大程度的因素使得所有其他因素在大O中无关，因此它变成O(sqrt(12nlogn))。一个不变的因素也是无关紧要的，所以它变成了O(sqrt(nlogn))。那么我想你可以使这个参数等于O(sqrt(n) * sqrt(logn))或O(sqrt(n) * log(n)^(1/2))，并且消除logn的功率得到O(sqrt(n)logn)。但我不知道最后一步的技术理由是什么，因为如果您可以将sqrt(logn)转换为logn，为什么不能将sqrt(n)转换为n？

来源

2011-02-24 19:50:08 mellamokb

提示：考虑扩展sqrt（1 + x）的主要条件为| x | < 1.

来源

2011-02-24 19:53:34

大O证明与开方和日志

回答

相关问题