带功能内部功能的大O分析

Question

我对处理功能内部功能（分析最坏情况时）的大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此整个区块的run（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 lg N)功能的O(N)迭代和O(N)固定时间操作。由于O(N lg N) > O(N)，O(N lg N) + O(N)简化为O(N lg 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 
}