gpt4 book ai didi

algorithm - O(1)+O(2)+ .... +O(n) 的阶和

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:54:47 27 4
gpt4 key购买 nike

总和 O(1)+O(2)+ .... +O(n) 的计算结果是什么?

我在某处看到它的解决方案:

O(n(n+1) / 2) = O(n^2)

但我对此并不满意,因为 O(1) = O(2) = constant,所以根据我的说法,它的计算结果必须仅为 O(n) .我在 Cormen 也看到过这个:

Σ(i=1 to n) O(i)

在上面的表达式中只有一个匿名函数。此函数与 O(1) + O(2) + ... + O(n) 不同,后者实际上没有清晰的解释。

最佳答案

这个问题似乎非常切合主题,因为有一个标签 asymptotic_complexity ...

根据 CLRS ,页。 49、

“表达式中匿名函数的个数理解为等于渐近符号出现的次数。例如,在表达式中

sum(O(i), i=1..n)

只有一个匿名函数(i 的函数)。因此,这个表达式与 O(1) + O(2) + ... + O(n) 不同,后者实际上没有清晰的解释”

实际上,在你的公式中,“O”符号后面的常数可能都是不同的,它们的增长可能会改变整个和的渐近行为。不要写这个!


为了更完整地回答您的问题,在 sum(O(i), i=1..n) 中,您可以使用以下事实(参见 GKP 第 450 页)

O(f(n)g(n)) = f(n) O(g(n))

因此,O(i) = i O(1),这次在您的公式中使用相同的 O(1)。因此,

sum(O(i), i=1..n) = sum(i, i=1, n) O(1)

=n(n+1)/2 O(1) = O(n^2)

这样你就可以毫不费力地消除你的总和。

关于algorithm - O(1)+O(2)+ .... +O(n) 的阶和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18757751/

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