使用函数内的函数进行Big-O分析

Question

我很困惑Big-O在处理函数内的函数时的工作原理(分析最坏情况时).例如,如果你有类似的东西怎么办？

for(int a = 0; a < n; a++)
{
    *some function that runs in O(n*log(n))*
    for(int b = 0; b < n; b++)
    {
        *do something in constant time*
    }
}

这整个块是否会在O(n ^ 2*log(n))中运行,因为在第一个for循环中,你有一个O(n)和一个O(n*log(n)),所以O(n*log (n))更大,因此我们采取的是什么？或者它是O(n ^ 3*log(n))因为你在外部for循环中有一个O(n)和一个O(n*log(n))？

任何帮助表示赞赏!谢谢!

Answer 1

它的

O(N) * (O(N lg N) + O(N) * O(1)) = O(N) * (O(N lg N) + O(N))
                                 = O(N) * O(N lg N)
                                 = O(N^2 lg N)

因为您有函数和常量时间操作的O(N)迭代.该简化为因.O(N lg N)O(N)O(N lg N) + O(N)O(N lg N)O(N lg N) > O(N)

Answer 2

在计算这种复杂性时,您应该添加内联或顺序函数并乘以嵌套函数.

例如,这将是O(n):

// O(n) + O(n) = O(2n)` which is `O(n)` (as constants are removed)
for (int i = 0; i < n; i++)
{ 
    /* something constant */ 
}
for (int j = 0; j < n; j++)
{ 
    /* something constant */ 
}

但是当函数嵌套时,会增加它们的复杂性:

// O(n) * O(n) = O(n^2)
for (int i = 0; i < n; i++)
{ 
    for (int j = 0; j < n; j++)
    { 
        /* something constant */ 
    }
}

你的例子是一个组合 - 你有一些嵌套在另一个函数中的顺序操作.

// this is O(n*logn) + O(n), which is O(n*logn)
*some function that runs in O(n*log(n))*
for(int b = 0; b < n; b++)
{
    *do something in constant time*
}

// multiplying this complexity by O(n)
// O(n) * O(n*logn)
for(int a = 0; a < n; a++)
{
    // your O(n*logn)
    // your b loop
}