1

只是为我的考试做一个快速的准备，例如我有：

f(x) = 5x<sup>2</sup> + 4x * log(x) + 2

大 O 是O(x<sup>2</sup> + x * log(x))还是应该考虑非对数系数，例如 5 或 4？

同样，考虑这段代码

for (int i = 0; i < block.length; i++)
    for (int j = 0; j < block.length;  j++)
        for (int k = 0; k < 5; k++)
             g(); //assume worst case time performance of g() is O(1)

那么大 O 是 O(5n 2 ) 还是 O(n 2 )？

4

2 回答 2

3

复杂性f(x) = 5x^2 + 4xlogx + 2是O(x^2)因为

O(g(x) + k(x)) = max(O(g(x), k(x))
// and O(X^2) > O(xlogx)

//additionally coeffs are disregarded
O(c*g(x)) = O(g(x))

因此，如果您有一个总和，您只需选择一天结束时最大的复杂度，当n趋于无穷大时，最大的组件将提供最多的计算负载。你是否有任何系数也没关系，因为你试图粗略估计会发生什么。

对于您的其他示例，请参见下面的推理

for (int i = 0; i < block.length; i++)
    for (int j = 0; j < block.length;  j++)
        for (int k = 0; k < 5; k++)
             g(); //assume worst case time performance of g() is O(1)

首先将循环转换为总和并从右到左计算总和

Sum (i=0,n)
    Sum(j=0, n)
        Sum(k=0, k=5)
            1

O(1) 从 1 到 5 的计数器仍然是 O(1)，记住你忽略 coeffs

Sum(k=0, k=5) 1 = O(5k) = O(1)

所以你最终得到了中间和，它计算了 O(1) n 次的函数，这给出了 O(n) 的复杂度

Sum(j=0, n) 1 = O(n)

最后你得到最左边的总和，注意到你计算了nn次，即n+n+n...，它等于n*n或n^2

Sum (i=0,n) n = O(n^2)

所以最终的答案是 O(n^2)。

于 2012-06-21T12:10:43.850 回答
0

O(x**2)因为：

lim n^2 if (x->8) = 8

lim 5n^2 if (x->8) = 8

8 is infinity

但是如果你有几个表达式的总和，你需要理解增长最快的函数。这将是你问题的答案。

表达式之前的任何其他常量都会给你相同的答案。在那种情况下，你应该使用渐近分析 我可以给你一个建议。如果您面临您需要的几个功能的总和：

  • 在组件上分解您的表达式
  • 想象每个元素的图
  • 了解增长最快的元素，不超过无限

这个元素会给你答案

于 2012-06-21T12:11:11.727 回答