Блог

Я хочу понять, как оценить сложность, big O, приведенного ниже алгоритма и как подойти к такого рода проблемам оценки big O в будущем с помощью подобных алгоритмов.

 #include <iostream>
 
std::size_t const jobSize = 3;
std::size_t jobCallCounter = 0;
std::size_t jobsDoneCounter = 0;
void doJob( std::size_t jobSize )
{
    jobCallCounter  ;
    for( std::size_t i = 0; i < jobSize;   i )
    {
        jobsDoneCounter  ;
    }
}
 
std::size_t recursiveCallCounter = 0;
std::size_t const cycleSize = 3;
void recursiveCall( std::size_t recursionNumber )
{
    recursiveCallCounter  ;
    if( !recursionNumber )
    {
        doJob( jobSize );
    }
    else
    {
        for( std::size_t i = 0; i < cycleSize;   i )
        {
            recursiveCall( recursionNumber - 1 );
        }
    }
}
 
int main()
{
    recursiveCall( 4 );
    std::cout << recursiveCallCounter << " recursive calls happened" << std::endl;
    std::cout << jobCallCounter << " job calls happened" << std::endl;
    std::cout << jobsDoneCounter << " jobs done" << std::endl;
}
 

Я понимаю, что общая сложность примерно равна O ( J * C ^ R ), где: J = jobSize , C = cycleSize , R = recursionNumber Что я изо всех сил пытаюсь понять, так это то, сколько рекурсивных вызовов происходит на каждом шаге базового цикла — цикл с самого первого вызова, где (в этом примере) recursionNumber = 4 .
Также мне интересно, как оценить количество doJob вызовов, также известных как . jobCallCounter
Спасибо!

Для этого вы можете найти рекурсивную формулу. Если временная сложность для задачи с R числом рекурсий и C размером цикла (это не вход для рекурсивной функции) обозначается T(R) , мы получим следующую рекурсивную формулу:

 T(R) = C* T(R-1)   1
 

И для начального случая рекурсии T(0) = J . 1 В формуле используется код проверки в коде.

Чтобы решить формулу, вы можете расширить ее:

 T(R) = C* (C * T(R-2)   1)   1 = C^2 T(R-2)   C  ‌ 1 
     = C^R T(0)   C^{R-1}   ...   C   1 = 
       C^R * J   C^{R-1}   ...   C   1  = O(C^R * J)
 

Обратите внимание, что as C и J не меняют свои значения во время рекурсии, мы не писали функцию сложности as T(R, C, J) , чтобы упростить решение рекурсии.