2.6 演習¶

2.6.1 確認問題¶

1. 反復と再帰の時間・空間計算量¶

次の 2 つのコードは、どちらも \(1 + 2 + \dots + n\) を計算します（\(n \ge 1\) とします）。n を 4 として、プログラムが実際に実行される順序に沿って次の問いに答え、2 つの書き方の効率を比較してください。

def sum_iter(n):
    s = 0
    for i in range(1, n + 1):
        s += i
    return s

def sum_recur(n):
    if n == 1:
        return 1
    return n + sum_recur(n - 1)

sum_iter(4) を実行すると、各ループの終了時に変数 s はそれぞれいくつになりますか？
sum_recur(4) を実行すると、どの関数が順に呼び出されますか？最も深い呼び出しから戻るとき、結果はどのように求められますか？
2 つの書き方の時間計算量と空間計算量は、それぞれいくつですか？問い 1、2 の実行過程と結び付けて理由を説明してください。

解答

ループ変数 i は 1、2、3、4 の順に変化し、各ループの終了時に s は 1、3、6、10 となります。したがって、sum_iter(4) は 10 を返します。
関数は sum_recur(4) → sum_recur(3) → sum_recur(2) → sum_recur(1) の順に呼び出されます。 sum_recur(1) が 1 を返した後、各呼び出しは順に 2 + 1 = 3、3 + 3 = 6、4 + 6 = 10 を得ます。最も深い呼び出しに到達した時点では、4 回の関数呼び出しはどれもまだ終了していません。
どちらのコードも、\(n\) に比例する回数のループまたは呼び出しを行うため、時間計算量はともに \(O(n)\) です。一方、空間計算量は異なります。反復版が使う変数は定数個だけなので \(O(1)\) です。再帰版では、終了条件に到達するまで、それまでの関数呼び出しが結果を待つ必要があります。そのため、呼び出しスタックには最大で \(n\) 回分の呼び出しが同時に保存され、空間計算量は \(O(n)\) です。

空間計算量を分析するときは、コード中の変数だけでなく、再帰呼び出しが使う空間も考える必要があります。

2. 3 つのコードの時間計算量¶

次の 3 つのコード片はいずれも、正の整数 \(n\) を入力とします。時間計算量が小さい順に並べ、それぞれの計算量を書いてください。

# コード片 1
s = 0
for i in range(n):
    s += i

# コード片 2
s = 0
for i in range(n):
    for j in range(i, n):
        s += j

# コード片 3
while n > 1:
    n = n // 2

解答

小さい順に、コード片 3 は \(O(\log n)\)、コード片 1 は \(O(n)\)、コード片 2 は \(O(n^2)\) です。コード片 3 では、ループのたびに \(n\) が半分になるため、ループ回数は約 \(\log_2 n\) 回です。コード片 1 のループはちょうど \(n\) 回実行されます。コード片 2 の内側のループ回数は順に \(n,n-1,\dots,1\) で、合計は \(n(n+1)/2\) となるため、二次の計算量です。

3. どちらの反転が空間を節約できるか¶

配列 nums のすべての要素を逆順にする方法として、次の 2 つがあります。

同じ長さの新しい配列 res を作り、逆順にコピーして返す。
2 つのインデックス i と j をそれぞれ先頭と末尾から中央へ動かし、nums[i] と nums[j] を順に交換する。

2 つの方法の空間計算量は、それぞれいくつですか？どちらが「インプレース」な操作ですか？

解答

入力と同じ長さの補助配列が必要なため、空間計算量は \(O(n)\) です。
使うのは 2 つのインデックス変数だけなので、空間計算量は \(O(1)\) であり、インプレースな操作です。

ただし、インプレースな反転は入力配列を変更します。入力の変更が許される場合にのみ優先して使うべきです。元の配列を残す必要がある場合は、方法 1 のコピーにかかる空間を省くことはできません。

2.6.2 プログラミング演習¶

1. フィボナッチ数¶

フィボナッチ数列は、\(F(0)=0\)、\(F(1)=1\) を満たし、\(n\ge2\) のとき \(F(n)=F(n-1)+F(n-2)\) となります。

0 以上の整数 n が与えられます。再帰を使わず、ループを使って \(F(n)\) を計算し、返してください。

解法のヒント

まず、n が 0 と 1 の場合をそれぞれ処理します
次の項の計算に必要なのは直前の 2 項だけで、数列全体を保存する必要はありません
2 つの変数を更新するときは、後で使う古い値を先に上書きしないよう注意します

LeetCode