帶功能內部功能的大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 
}