[解決済み] 再帰的関数の複雑さの決定（Big O記法）

質問

明日、コンピュータサイエンスの中間試験を受けるのですが、これらの再帰的な関数の複雑さを判断するのを手伝ってほしいのです。簡単なケースの解き方は知っているのですが、これらの難しいケースの解き方をまだ学んでいないのです。これらは、私が理解できなかった例題のほんの一部です。どんな助けでもありがたく、私の勉強に大いに役立つことでしょう。

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

解決方法は？

各関数の時間計算量（Big O記法）。

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

この関数は基本ケースに到達するまでにn回再帰的に呼び出されるので、その O(n) と呼ばれることが多い。 線形 .

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

この関数は毎回n-5ずつ呼ばれるので、nから5を引いてから呼び出すが、n-5も O(n) . (実際には n/5 回のオーダーと呼ばれる。そして、O(n/5) = O(n) ).

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

この関数は log(n) base 5 で、毎回 5 で割っています。 を呼び出す前に、その O(log(n)) (5進数)と呼ばれることが多い。 対数的 であり、Big O記法や複雑性解析では2進数を使うことがほとんどです。

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

ここで、それは O(2^n) または 指数的 各関数呼び出しは、再帰されない限り、自分自身を2回呼び出すので n 回です。

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

そして、ここでforループは2ずつ増えていくのでn/2かかり、再帰はn/5かかり、forループは再帰的に呼ばれるので、したがって時間複雑度は

(n/5) * (n/2) = n^2/10 となります。

漸近挙動や最悪シナリオの考慮、あるいは big O が目指している上界により、我々は最大の項にしか興味がないので O(n^2) .

中間テスト頑張ってください;)