logo标签列表

O(1)+O(2)+ .... +O(n)的阶数之和

algorithmbig-oasymptotic-complexity
5

求和 O(1)+O(2)+ .... +O(n) 的结果是什么？

我曾在某处看到过它的解法，写着：

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

但是我对它不满意，因为O(1) = O(2) = 常数，所以在我看来，它只能评估为O(n)。 我在Cormen的书中也看到过这一点：

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

以上表达式只有一个匿名函数。这个函数与 O(1) + O(2) + ... + O(n) 不同，后者没有清晰的解释。

1
可能是一个问题，需要在http://math.stackexchange.com/上提问。 - d-stroyer
1
这个问题似乎不适合讨论，因为它涉及到数学。 - Sean Owen
这是关于计算机科学中的数学问题 :) - sodik
如果这是用于计算时间复杂度的大O符号，那么这个问题可能更适合在http://programmers.stackexchange.com/上提问。 - Some programmer dude
这个问题似乎不太适合，因为它更多是概念性的，可能更适合发布在http://programmers.stackexchange.com/上。 - Some programmer dude
显示剩余2条评论
4个回答
4
这个问题似乎非常符合主题，因为存在标签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 p. 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)
这样，您就可以轻松消除您的总和。
“O（）符号中的常数可能完全不同”，O（。）产生一个集合，而不是一个值。“常数”本身并不存在。 - user824425
2
实际的困惑源于在展开求和时，n 不再被视为表示输入大小的参数，而是作为一个基数常量。因此，你实际上拥有一个可数无限的扩展系列，每个输入大小对应一个扩展，这并不是描述复杂度的好工具。然而，你仍然可以正式地操作大O符号背后的定义。 - collapsar
@Rhymoid。O(n)是一组函数家族，但f∈O(n)实际上意味着存在一个常数M，使得f(n) <= M g(n)。至少这是所有作者都说的，包括我在答案中指出的两本书，还有Knuth TAOCP和Aho、Hopcroft和Ullman。 - user1220978
该常量在集合的定义中存在本体绑定。O(.)的参数实际上是一个函数，而另一个函数可以在该集合中。应该写成O(n :> n)（n映射到n），而不是O(n)，但为了方便起见，这种绑定是隐含的。严格来说，如果您已经将n绑定到一个值并编写O(n)，则您拥有O(1)的子集（更正式地，O(x :> 1)）。我看到过很多次对此解释不够准确（甚至错误），常常让我的同学感到困惑。我认为TAOCP没有不同的解释，只是不够精确。 - user824425
总之：对于 O(.)，有许多解释，有些精确，有些简短。这个问题需要一个非常精确的 O(.) 定义，TAOCP 没有给出（或者你引述不正确）。 （此外，我的解释受函数式编程的影响很大。） - user824425
2
根据大O符号的定义进行翻译。
你有n个函数f_i，每个函数都满足：
a_i * i <= f_i(x) <= b_i * i; x > X_i

对于一些正常数 a_i, b_i 和足够大的 X_i，令 X = max_i ( X_i ) 并对 n 个不等式求和，得到：

sum_i=1..n ( a_i * i ) <= sum_i=1..n ( f_i(x) ) <= sum_i=1..n ( b_i * i )

注意到
sum_i=1..n ( min(a_i) * i ) <= sum_i=1..n ( a_i * i )
sum_i=1..n ( b_i * i )      <= sum_i=1..n ( max(b_i) * i )

抵达

    min(a_i) * 0.5*(n(n-1))  <= sum_i=1..n ( f_i(x) ) <= max(b_i) * 0.5*(n(n-1))
<=>       A       * (n(n-1)) <= sum_i=1..n ( f_i(x) ) <=        B      *(n(n-1))

因此，您开始的这些函数的总和确实是 O(n^2)。
0

当然，O(1)和O(2)是常数，所以我们可以忽略它们。但是O(n/2)是常数吗？我想不是。因此，尝试（在你的作业中）仅计算元素的后一半：

O(n/2) + O(n/2+1) + ... O(n) = ??

你会想出 O(n^2) :)

0

有一个技巧可以找到这个公式，真的不难。

你有：

1 + 2 + 3 + 4 + .... + n

如果你把这个列表数两次（一次从低到高排序，一次从高到低排序），你会得到两倍的结果。

((1 + 2 + 3 + 4 + ... + n) + (n + (n - 1) + (n - 2) ... + 2 + 1)) / 2

这与下面的公式相同：

((1 + n) + (2 + n - 1) + (3 + n - 2) + ... + (n + 1)) / 2

而这是：

((n + 1) * n) / 2

或者我们用O(n²)表示。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接