复杂度分析-考虑非对数因子 [英] Complexity analysis - take consideration of non logarithmic factor

问题描述

例如，为我的考试做一个快速准备:

Just a quick preparation for my exam, for example I have:

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

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

Would the big O be O(x<sup>2</sup> + x * log(x)) or should I take consideration of non-logarithmic coefficients such as 5 or 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 ² )还是O(n ² )?

So would the big O be O(5n²) or O(n²)?

推荐答案

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 达到无穷大时，最大的分量将提供最大的计算负荷.您是否有任何系数也无关紧要，因为您尝试粗略地估计将要发生的事情.

So if you have a sum you just select the largest complexity as at the end of the day, when n goes to infinity the largest component will give the most computational load. It also doesn't matter if you have any coeffs because you try to roughly estimate what's going to happen.

---

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

---

For your other sample see reasoning below

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)

首先convert循环成和，然后从右到左求和

First convert loops into sums and work out the sums from right to left

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

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

Counter of O(1) from 1 to 5 is still O(1), remember you disregard coeffs

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

因此，您得到的是中间总和，该总和是O(1)的n次，因此复杂度为O(n)

So you end up with the middle sum, which counts a function of O(1) n times, this gives the complexity of O(n)

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

最后，您获得最左边的总和，并注意到您计数了 n n 次，即n+n+n...，它等于n*n或n^2

Finally you get to the leftmost sum and notice that you count n n-times, i.e. n+n+n..., which is equal to n*n or n^2

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

所以最后的答案是O(n ^ 2).

So the final answer is O(n^2).

这篇关于复杂度分析-考虑非对数因子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！