总和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)没有真正清晰解释的功能不同。
问问题
2646 次
4 回答
4
这个问题似乎完全是主题，因为有一个标签asymptotic_complexity ...
根据CLRS，p。49,
“表达式中匿名函数的数量被理解为等于渐近符号出现的次数。例如，在表达式中
总和（O（i），i = 1..n）
只有一个匿名函数（i 的函数）。因此，此表达式与 O(1) + O(2) + ... + O(n) 不同，后者实际上并没有清晰的解释”
实际上，在您的公式中，“O”符号后面的常数可能都是不同的，它们的增长可能会改变整个和的渐近行为。不要写这个！
为了更完整地回答您的问题，总而言之（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)
这样您就可以毫无困难地消除您的总和。
于 2013-09-12T07:40:34.440 回答
2
根据 Big-Oh 符号的定义。
你有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).
于 2013-09-12T07:39:12.097 回答
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²) 的概念中所说的那样。
于 2013-09-12T13:34:36.193 回答
0
当然，O(1) 和 O(2) 是一个常数，所以我们可以忘记它们。但是 O(n/2) 是常数，我猜不是。所以试着（为你的作业）只计算元素的后半部分：
O(n/2) + O(n/2+1) + ... O(n) = ??
你会想出O(n^2):)
于 2013-09-12T07:22:16.443 回答