再帰アルゴリズムの時間計算量について十分に理解していない

[[414048]]

この記事では、面接の質問と面接のシナリオを使用して、再帰アルゴリズムの時間計算量を計算する方法を分析します。

多くの学生は再帰アルゴリズムの時間計算量について非常に漠然としていると思うので、この記事ではカールが徹底的に説明します。

同じ質問に対して、同じ再帰アルゴリズムを使用すると、O(n) コードを書く生徒もいれば、O(logn) コードを書く生徒もいます。

これはなぜでしょうか?

再帰の時間計算量を十分に理解していないと、このようなことが起こります。

次に、簡単な面接の質問を使用して面接のシナリオをシミュレートし、再帰アルゴリズムの時間計算量を徐々に分析して、最終的に最適なソリューションを見つけ、同じ再帰を O(n) コードとして記述する方法を確認します。

面接の質問: x の n 乗を求めてください

このような単純な質問について考えてみましょう。コードはどのように記述すればよいでしょうか?最も直感的な方法は、 for ループを使用して結果を見つけることです。コードは次のとおりです。

 int関数1( intx , intn ){
 int result = 1; // 0 乗した数値はどれも 1 になることに注意してください
( int i = 0; i < n; i++)の場合{
        結果 = 結果 * x;
    }
結果を返します。
 }

時間計算量は O(n) です。このとき、面接官はより効率的なアルゴリズムがあるかどうかを尋ねます。

現時点でアイデアがない場合は、「できません」「わかりません」などと言わないでください。

これについて面接官と話し合い、「ヒントをもらえますか？」と尋ねることができます。面接官のプロンプト: 「再帰アルゴリズムについて考えてください。」

次に、次のような再帰アルゴリズムを記述し、再帰を使用してこの問題を解決します。

 int関数2( intx , intn ){
    (n == 0)の場合{
 return 1; // 1を返すこれも0が1に等しいためである
    }
関数2(x, n - 1) * xを返します。
 }

インタビュアーはこう尋ねました。「それでは、このコードの時間計算量はどれくらいですか?」

再帰を見ると O(logn) を思い浮かべる学生もいるかもしれません。実際はそうではありません。再帰アルゴリズムの時間計算量は、基本的に、再帰の数 * 各再帰の操作の数によって決まります。

では、もう一度コードを見てみましょう。ここでは何回再帰しているでしょうか?

n-1 ごとに再帰が n 回実行され、時間の計算量は O(n) です。乗算演算が実行されるたびに、乗算演算の時間計算量は定数項 O(1) であるため、このコードの時間計算量は n * 1 = O(n) です。

この時間の複雑さは面接官の期待に応えられませんでした。そこで、次の再帰アルゴリズムコードを書きました。

 int関数3( intx , intn ){
    (n == 0)の場合{
 1 を返します。
    }
    (n % 2 == 1)の場合{
 function3(x, n / 2) * function3(x, n / 2)*x を返します。
    }
 function3(x, n / 2) * function3(x, n / 2) を返します。
 }

これを見た面接官は微笑んで「このコードの時間計算量はどれくらいですか？」と尋ねました。この瞬間、深い考えに陥る学生もいるかもしれません。

分析してみましょう。まず、再帰が何回実行されるかを見てみましょう。再帰を完全な二分木に抽象化できます。学生が書いたアルゴリズムは、図に示すように、完全な二分木で表すことができます (表現の便宜上、n は偶数 16 に選択されています)。

現在のバイナリツリーは、x の n 乗を求めるものです。n が 16 の場合、乗算演算はいくつ実行されますか。

このツリー内の各ノードは再帰と乗算演算を表すため、再帰の数はツリー内のノードの数によって異なります。

バイナリツリーに精通している場合は、完全なバイナリツリーのノードの数を計算する方法を知っている必要があります。この完全なバイナリツリーのノードの数は、2^3 + 2^2 + 2^1 + 2^0 = 15 です。これは実際には等比数列の和の式であることがわかります。この結論は、バイナリツリーに関連する面接の質問でよく出てきます。

では、x の n 乗を求める場合、この再帰ツリーにはいくつのノードがあるでしょうか? 次の図に示すように: (m は深さで、0 から始まります)

定数項 -1 を無視した後でも、この再帰アルゴリズムの時間計算量は O(n) のままです。はい、正しくお読みいただけました。依然として O(n) の時間計算量です。

この時点で、面接官は「この再帰アルゴリズムは依然として O(n) です」と言うでしょうが、これは明らかに面接官の期待を満たしていません。

では、O(logn) 再帰アルゴリズムをどのように記述すればよいでしょうか?

先ほど示した再帰アルゴリズムのコードについて考えてみましょう。冗長性はありますか? 実際、繰り返し計算がいくつかあります。

そこで、次の再帰アルゴリズムコードを書きました。

 int関数4( intx , intn ){
    (n == 0)の場合{
 1 を返します。
    }
 int t = function4(x, n / 2); // function3と比較すると、再帰演算が抽出されます
    (n % 2 == 1)の場合{
 t * t * xを返します。
    }
 t * tを返します。
 }

ここで、このコードの時間計算量を見てみましょう。

再帰回数を引き続き見てみると、ここでは再帰呼び出しが 1 回だけであり、そのたびに n/2 であることがわかります。つまり、ここでは 2 を底とする n の対数を合計回呼び出していることになります。

各再帰演算は乗算演算であり、定数演算でもあります。したがって、この再帰アルゴリズムの時間計算量は、まさに O(logn) です。

この時点で、全員がようやくこのようなコードを書いて、時間の計算量を非常に明確に分析しました。面接官はかなり満足していると思います。

要約する

結局のところ、初心者は再帰の時間計算量について混乱することがありますし、多くの問題を練習したベテランでさえもまだ混乱しています。

この記事では、非常に簡単な面接の質問「x の n 乗を求める」を使用して、再帰アルゴリズムの時間計算量を段階的に分析します。再帰を見たときに O(logn) を考えないように注意してください。

再帰を使用すると、O(logn) のコードを書くことができる生徒もいれば、O(n) のコードを書くことができる生徒もいます。

function3 のような再帰実装の場合、これは O(logn) の時間計算量であると感じることは簡単ですが、実際には O(n) アルゴリズムです。

 int関数3( intx , intn ){
    (n == 0)の場合{
 1 を返します。
    }
    (n % 2 == 1)の場合{
 function3(x, n / 2) * function3(x, n / 2)*x を返します。
    }
 function3(x, n / 2) * function3(x, n / 2) を返します。
 }