関数内の関数を使った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）の）、ループの最初の内、あなたはO（n）を持っているためとO（n * log（n））であるので、O（n * log（n））は大きいので、または、外側のforループ内にO（n）とO（n * log（n））があるので、O（n^3 * log

ご協力いただきましてありがとうございます。ありがとう！

Answer 1

あなたがO(N lg N)機能のO(N)の反復とO(N)、一定時間操作を持っているのでそれは

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 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 
}