循环递归调用：大O算法及其步骤

Question

我想了解如何评估以下算法的复杂性、大 O 以及如何在未来使用类似算法来处理大 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 我努力做到的comprehend 是在基本循环的每个步骤上发生了多少递归调用 - 从第一个调用开始的循环，其中（在本例中）recursionNumber = 4。此外，我对如何评估 doJob 调用量 a.k.a 很感兴趣。 jobCallCounter。谢谢！

Answer 1

你可以找到一个反推公式。如果 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)

注意，由于C和J在递归过程中没有改变它们的值，我们没有把复杂度函数写成T(R, C, J)，为了简化递归求解.

循环递归调用：大O算法及其步骤

recursive call from cycle: big O of algorithm and its steps

c++

algorithm

recursion

big-o

cycle