Big-O анализ с функциями внутри функций - PullRequest
Новая
       3

Big-O анализ с функциями внутри функций

5 голосов
/ 20 сентября 2011

Я запутался в том, как работает 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)), потому что у вас есть O (n) и O (n * log (n)) внутри внешнего цикла for?

Любая помощь приветствуется!Спасибо!

Ответы [ 2 ]

10 голосов
/ 20 сентября 2011

Это 

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).

5 голосов
/ 20 сентября 2011

При вычислении этого типа сложности вам следует добавить встроенных или последовательных функций и умножить вложенных функций.

Например, это будет 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
}
...