ビッグ・オー記法を学ぶ

生成AIは本当に便利で、使っていて楽しいですね。
一方で、レビュー側に回ることになった人間としては頭を抱えることも多いのではないでしょうか。
その中の一つに計算量があると思います。
改めてビッグ・オーを学ぶことで、生成AIが出力したコードを疑えるようになろう！

という、本日行う社内勉強会に向けた資料です。突貫で作成。

ビッグ・オーとは

プログラムの性能を記述するために使う表記方法のことです。
次のような表記を見たことがあるのではないでしょうか。

$$O(N),O(logN),O(N2),O(2N) O(N), O(logN), O(N^2), O(2^N)$$

3つの計算量

時間計算量

プログラムの実行時間。
喫茶店で例えるなら、お客さんの数に対して作業時間がどう変化するか。

$$O(1):お客さんの数に関係なく、同じ時間で完了する作業 O(1): お客さんの数に関係なく、同じ時間で完了する作業$$

エスプレッソマシンなどの電源を入れる時間は、何杯作るかに関わらず同じ。

$$O(N):お客さんの数に比例して時間が増える作業 O(N): お客さんの数に比例して時間が増える作業$$

一人ひとりの注文を受けて、1杯ずつ提供するなら、10人なら10倍の時間がかかる。

$$O(N2):お客さんの数の二乗に比例して時間が増える作業 O(N^2): お客さんの数の二乗に比例して時間が増える作業$$

各お客さんに全種類のコーヒー豆の味の違いを説明するなら、お客さんの数×コーヒー豆の数になる。

空間計算量

プログラムに要求されるメモリ量。
喫茶店で例えるなら、お客さんの数に対して必要なリソースがどう変化するか。

$$O(1):お客さんの数に関係なく、同じ量のリソースで対応できる O(1): お客さんの数に関係なく、同じ量のリソースで対応できる$$

抽出器具は1台あれば、何人分のコーヒーを作るにも同じ器具を使いまわせる。

$$O(N):お客さんの数（注文数）に比例して、リソースが必要になる O(N): お客さんの数（注文数）に比例して、リソースが必要になる$$

お客さんの数だけカップは必要になる。

$$O(N2):お客さんの数の二乗に比例してリソースが必要になる O(N^2): お客さんの数の二乗に比例してリソースが必要になる$$

各お客さんに全種類のコーヒーのサンプルを少量ずつ提供する場合、お客さんの数×コーヒーの数分のカップが必要になる。

償却計算量

プログラム一連の動作の流れを考慮した計算量。
喫茶店で例えるなら、たまに大きなコストがかかる作業があっても、平均的に見れば効率が良い場合の計算量。
注文の度に焙煎をするのではなく、予め焙煎をしておく的な話です。

計算量の増加をグラフで捉える

累乗、階乗の計算時間は非常に多くなる。
自分のコード、あるいはレビューするコードの計算量はどうなっているか？
PoCレベルであればそこまで気になりませんが、本番開発ではユーザ体験に影響を及ぼしたり、タイムアウトやスタックオーバーフローに繋がるリスクがあります。意識したいですね。

Pythonによるビッグ・オー実践問題集

習うより慣れよ

ということで、ひたすらに問題を解く中で理解を深めていきましょう。

問題は下記の本を参考にさせていただきました。コードはJavaからPythonに書き換えています。

https://www.amazon.co.jp/dp/4839960100

問1

次の関数の時間計算量はなんでしょうか。

def foo(array):
    sum = 0
    product = 1
    
    for i in range(len(array)):
        sum += array[i]
    
    for i in range(len(array)):
        product *= array[i]
    
    print(f"{sum} * {product}")

回答・解説

このコードの時間計算量は O(n) です。

この関数は配列（リスト）を受け取り、まず最初のループで全要素の合計を計算し、次のループで全要素の積を計算します。そして最後に「合計 * 積」という形式で出力します。
なぜなら、配列の長さに比例した2つの独立したループがあり、それぞれ O(n) の時間がかかるためです。
合計で O(n) + O(n) = O(2n) となり、ビッグO記法では定数係数を無視するので O(n) です。

問2

次の関数の時間計算量はなんでしょうか。

def print_pairs(array):
    for i in range(len(array)):
        for j in range(len(array)):
            print(f"{array[i]} + {array[j]}")

回答・解説

このコードの時間計算量は O(n²) です。

外側のループ: 配列の長さ n 回実行されます (i = 0 から n-1 まで)
内側のループ: 各 i に対して、配列の長さ n 回実行されます (j = 0 から n-1 まで)
内側の処理（print文）: O(1) の定数時間

したがって、総実行回数は n × n = n² 回となり、時間計算量は O(n²) です。

問3

次の関数の時間計算量はなんでしょうか。

def print_unordered_pairs(array):
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            print(f"{array[i]} + {array[j]}")

回答・解説

このコードの時間計算量は O(n²) です。

外側のループ: 配列の長さ n 回実行されます (i = 0 から n-1 まで)
内側のループ: i の値に依存して実行回数が変化します

i = 0 のとき: n-1 回
i = 1 のとき: n-2 回
i = 2 のとき: n-3 回
...
i = n-2 のとき: 1 回
i = n-1 のとき: 0 回

内側のループの合計実行回数は: (n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2 回
したがって、時間計算量は O(n²) ですが、定数係数として 1/2 があるため、前の例よりも実行時間が約半分になります。ただし、ビッグO表記では定数係数は無視されるため、表記上は同じ O(n²) になります。

問4

次の関数の時間計算量はなんでしょうか。

def print_unordered_pairs(array1, array2):
    for i in range(len(array1)):
        for j in range(len(array2)):
            if array1[i] < array2[j]:
                print(f"{array1[i]} + {array2[j]}")

回答・解説

このコードの時間計算量は O(n×m) です。

外側のループ: array1の長さを n とすると、n 回実行されます (i = 0 から n-1 まで)
内側のループ: array2の長さを m とすると、各 i に対して m 回実行されます (j = 0 から m-1 まで)
条件判定と出力: 各ループの組み合わせごとに O(1) の定数時間

したがって、総実行回数は最大で n × m 回となり、時間計算量は O(n×m) です。
特殊なケースとして、両方の配列の長さが同じ (n = m) 場合は、時間計算量は O(n²) になります。

問5

次の関数は、配列を逆順に並び替えるものです。
時間計算量はなんでしょうか。

def reverse(array):
    for i in range(len(array) // 2):
        other = len(array) - 1 - i
        temp = array[i]
        array[i] = array[other]
        array[other] = temp

回答・解説

このコードの時間計算量は O(n) です。

ループ: 配列の長さの半分（n/2）回実行されます
各ループの処理:

インデックス計算: O(1)
値の交換: O(1)

したがって、総実行時間は O(n/2) = O(n) です。ビッグO表記では定数係数（ここでは1/2）は無視されます。

問6

各文字列をソートし、その後配列全体をソートするアルゴリズムの計算量を考えてみてください。

回答・解説

def sort_strings_and_array(string_array):
    # 各文字列をソート
    sorted_strings = []
    for string in string_array:
        sorted_string = ''.join(sorted(string))
        sorted_strings.append(sorted_string)
    
    # 配列全体をソート
    sorted_strings.sort()
    
    return sorted_strings

パラメータ定義
n: 配列内の文字列の数
m: 最長の文字列の長さ

1. 各文字列のソート
   各文字列のソートは一般的に O(m log m) の時間がかかります（比較ベースのソートアルゴリズムの場合）
   n個の文字列それぞれをソートするので、この部分の計算量は O(n × m log m)

2. 配列全体のソート:
   n個の文字列をソートするので、この部分の計算量は O(n log n)
   ただし、各比較操作は最大で O(m) の時間がかかる可能性があります（文字列同士の比較）
   したがって、この部分の計算量は O(n log n × m)

3. 合計時間計算量:
   O(n × m log m) + O(n log n × m)
   よって総時間計算量は O(n × m(log n + log m)) となります

具体例
["cat", "dog", "bat", "rat"] の場合：

各文字列をソート: ["act", "dgo", "abt", "art"]
配列全体をソート: ["abt", "act", "art", "dgo"]

これは文字列の内部でアナグラム（文字の順序を変えた言葉）をグループ化するような問題にも応用できます。例えば、アナグラムをグループ化する場合は、ソートした文字列を辞書のキーとして使用することもできます。

問7

次の関数は、平衡二分探索木においてすべてのノードの値を合計するものです。
時間計算量と空間計算量はどうなるでしょうか。

def sum(node):
    if node == None:
        return 0
    return sum(node.left) + node.value + sum(node.right)

回答・解説

時間計算量
このコードの時間計算量は O(n) です。ここで n は木のノード数です。

1. ベースケース:
   ノードが None の場合 (葉ノードの子や空の木)、O(1) で即座に 0 を返します

2. 再帰ケース:
   各ノードで:

• 左部分木の合計を計算 (再帰呼び出し)
• 現在のノードの値を取得 (O(1))
• 右部分木の合計を計算 (再帰呼び出し)
• 結果を合計 (O(1))

木のすべてのノードを1回ずつ訪問するため、総計算量は O(n) となります。

空間計算量
空間計算量は O(h) です。ここで h は木の高さです。

1. 再帰呼び出しによりコールスタックが使用される
2. スタックの最大深さは木の高さ h に比例
3. 各スタックフレームは定数サイズのメモリを使用

最悪の場合（完全に不均衡な木、リストのような形状）では h = n となり、空間計算量は O(n) になります。
最良の場合（完全バランス木）では h = log(n) となり、空間計算量は O(log n) になります。

再帰処理の特徴
この関数は典型的な後順走査（Post-order traversal）の形式で木を処理しています：

1. 左部分木を処理
2. 右部分木を処理
3. 現在のノードを処理

この再帰パターンは、木構造のデータを下から上へ集約するような処理（例：合計、最大値/最小値の計算、高さの計算など）によく使われます。

最適性について
このアルゴリズムは時間計算量の観点からは最適です。二分木のすべてのノードの値を合計するためには、少なくとも各ノードを1回は訪れる必要があるため、O(n) より良い時間計算量は達成できません。
空間計算量は再帰の特性上 O(h) となりますが、イテレーティブな実装（スタックを明示的に使用）に変更することで同じ機能を維持したまま潜在的にメモリ使用量を最適化できる可能性があります。

問8

次の関数は、ある数についてそれよりも小さい数で割り切れるかを調べることで、その数が素数であるかを調べるものです。
この関数の時間計算量はなんでしょうか。
また、この関数を最適化したコードを考えてみてください。

def is_prime(n):
    for x in range(2, n):
        if n % x == 0:
            return False
    return True

回答・解説

このコードの時間計算量は O(n) です。

1. for ループ: 2 から n-1 まで最大 (n-2) 回実行されます
2. 各ループでの処理（割り算と余りの計算）: O(1)
3. 最悪の場合（nが素数の場合）、全てのループが実行されます

したがって、最悪の場合の時間計算量は O(n) となります。

関数の最適化

数学的に、合成数（素数でない数）は必ず √n 以下の約数を持つため、x の上限を n から √n に減らせます。これにより時間計算量が O(√n) に改善されます。

def is_prime_optimized(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    
    # 2と3の倍数を除外する簡単なチェック
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    # 6k±1の形の数のみをチェック
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    
    return True

合成数が必ず√n以下の約数を持つことの証明
まず、合成数の定義から始めましょう。合成数とは、1と自分自身以外の約数を持つ自然数のことです。

任意の合成数 n について考えます。n が合成数であるため、n = a × b という形で表すことができます。ここで a と b は 1 < a, b < n を満たす自然数です。
この a と b について、次の3つのケースを考えます：

ケース1: a ≤ √n かつ b ≥ √n の場合
この場合、a は√n以下の約数となるため、n は√n以下の約数を持ちます。

ケース2: a > √n かつ b > √n の場合
この場合、a × b > √n × √n = n となります。
しかし、これは n = a × b という前提と矛盾します。
つまり、a と b の両方が√n より大きいということはありえません。

ケース3: a < √n かつ b < √n の場合
この場合、a × b < √n × √n = n となります。
これも n = a × b という前提と矛盾するため、ありえません。

したがって、唯一可能なのは、a と b の少なくとも一方が√n以下であるケースです。
つまり、任意の合成数 n は必ず√n以下の約数を持つと証明されました。

具体例
例として、合成数 n = 24 を考えてみましょう。
√24 ≈ 4.9 なので、24は必ず5未満の約数を持つはずです。
実際に24の約数は：1, 2, 3, 4, 6, 8, 12, 24 です。
このうち 2, 3, 4 は√24以下であり、証明と一致しています。
これが、素数判定アルゴリズムで√nまでしか調べなくても良い理由です。√n以下に約数がなければ、それ以上に約数が存在することはないため、その数は素数と判定できます。

問9

次の関数はn!を計算します。
時間計算量はなんでしょうか。

def factorial(n):
    if n < 0:
        return -1
    elif n == 0:
        return 1
    else:
        return n * factorial(n - 1)

回答・解説

このコードの時間計算量は O(n) です。

1. ベースケース: n < 0 または n == 0 の場合、O(1) で即座に結果を返します
2. 再帰ケース: n > 0 の場合

• factorial(n-1) を計算するために再帰呼び出しを行います
• 再帰の深さは n に比例し、n, n-1, n-2, ..., 1, 0 と呼び出されます
• 各再帰レベルでの追加処理（乗算）は O(1) です

したがって、総実行時間は再帰の深さ n に比例し、時間計算量は O(n) となります。

問10

次の関数は、ある文字列の順列をすべて表示します。
時間計算量はなんでしょうか。

def permutation(string):
    permutation_helper(string, "")

def permutation_helper(string, prefix):
    if len(string) == 0:
        print(prefix)
    else:
        for i in range(len(string)):
            rem = string[0:i] + string[i+1:]
            permutation_helper(rem, prefix + string[i])

回答・解説

このコードの時間計算量は O(n² × n!) です。

まず、permutation_helper 関数の呼び出し回数を考えます：

1. 最初のレベル：1回呼び出されます（最初の呼び出し）
2. 2番目のレベル：n回呼び出されます（各文字を1番目に選ぶ）
3. 3番目のレベル：n × (n-1)回呼び出されます（最初の文字を選び、次に残りから選ぶ）
4. 4番目のレベル：n × (n-1) × (n-2)回呼び出されます
5. ...

合計すると、再帰呼び出しの総数は：
1 + n + n(n-1) + n(n-1)(n-2) + ... + n! = O(n!)

次に、各呼び出しの中で行われる操作を考えます：

1. 条件チェック：O(1)
2. for ループの実行：最大 n 回
3. 各ループ内部での処理：
   • 部分文字列の作成（string[0:i] + string[i+1:]）：O(n)

• 文字列連結（prefix + string[i]）：O(n)
• 合計：O(n)

4. 従って、各呼び出しの中での総処理時間：O(n × n) = O(n²)

したがって、総時間計算量は
呼び出し回数 × 各呼び出しでの処理時間 = O(n!) × O(n²) = O(n² × n!)
これは、特に長い文字列に対して、文字列の連結と部分文字列の作成が重要な要素となるためです。

アルゴリズムの説明
このアルゴリズムは以下のように動作します：

空文字列から始め、再帰的に文字列の順列を構築
各ステップで、残りの文字から1つ選び、それを現在のプレフィックスに追加
選んだ文字を残りの文字列から取り除き、新しいプレフィックスと残りの文字列で再帰
残りの文字がなくなったら、完成した順列（プレフィックス）を出力

具体例
例えば「abc」の順列を考えると：

permutation("abc", "")
  i=0: permutation("bc", "a")
    i=0: permutation("c", "ab")
      i=0: permutation("", "abc") → 出力 "abc"
    i=1: permutation("b", "ac")
      i=0: permutation("", "acb") → 出力 "acb"
  i=1: permutation("ac", "b")
以下同様...

これにより、"abc", "acb", "bac", "bca", "cab", "cba" という6つの順列がすべて生成されます。

このアルゴリズムは、組み合わせ最適化問題や辞書ベースの攻撃など、あらゆる可能な順列を生成する必要があるアプリケーションで使用されます。

問11

次の関数は、N番目のフィボナッチ数を求めます。
時間計算量はなんでしょうか。
また、最適化方法を考えてみてください。

def fib(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

回答・解説

このコードの時間計算量は O(2ⁿ) です。

正確には Θ(φⁿ) ですが、O(2ⁿ) という表記が一般的に使われます（φは黄金比≈1.618）

再帰木を考えると、fib(n) は fib(n-1) と fib(n-2) を呼び出します
fib(n-1) は fib(n-2) と fib(n-3) を呼び出します
以下同様に続きます

この再帰呼び出しは指数関数的に増加し、バイナリツリー状の呼び出し構造を形成します。再帰の深さは n であり、最悪の場合、各レベルで呼び出し数が2倍になるため、O(2ⁿ) の時間計算量となります。

最適化方法

1. 動的計画法（メモ）
   計算済みの結果をキャッシュして再利用します。時間計算量が O(n) に改善されます。

def fib_memoized(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    memo[n] = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo)
    return memo[n]

2. 反復的実装
   再帰の代わりにループを使用します。これも時間計算量が O(n) で、空間計算量も O(1) に改善されます。

def fib_iterative(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

問12

次の関数は、nまでの2のべき乗を表示します。
時間計算量と空間計算量はどうなるでしょうか。

def power_of_2(n):
    if n < 0:
        return 0
    elif n == 0:
        print(1)
        return 1
    else:
        prev = power_of_2(n // 2)
        curr = prev * 2
        print(curr)
        return curr

回答・解説

時間計算量
このアルゴリズムの時間計算量は O(log n) です。

1. 再帰の深さ：
   この関数は n を繰り返し半分（n//2）にしていくため、再帰の深さは log₂n となります

2. 各再帰レベルでの処理：

• 四則演算（乗算、除算）：O(1)
• 出力処理（print）：O(1)

したがって、総計算量は再帰の深さに比例し、O(log n) となります。

空間計算量
空間計算量も O(log n) です。

1. 再帰のコールスタック：
   最大深さは log₂n

2. 各スタックフレームで使用される変数（prev, curr）：
   定数サイズのメモリ

したがって、必要なスタック空間は再帰の深さに比例し、O(log n) となります。

問13

次の関数の時間計算量と空間計算量はなんでしょうか。

def product(a, b):
    sum = 0
    for i in range(b):
        sum += a
    return sum

回答・解説

時間計算量
このコードの時間計算量は O(b) です。

1. for i in range(b) によって、ループが b 回実行されます
2. ループ内の処理（sum += a）は定数時間 O(1) です
3. よって全体の時間計算量は O(b) となります

空間計算量
このコードの空間計算量は O(1) です：

• 使用している変数は sum と i の2つだけで、入力サイズに関係なく一定のメモリしか使用しません
• 追加のデータ構造も使っていません

問14

次の関数の時間計算量と空間計算量はなんでしょうか。

def power(a, b):
    if b < 0:
        return 0  # エラー（負の指数は対応していない）
    elif b == 0:
        return 1  # 任意の数の0乗は1
    else:
        return a * power(a, b - 1)  # 再帰的に計算

回答・解説

時間計算量
このコードの時間計算量は O(b) です。

• 基本ケース（b < 0 または b == 0）は定数時間 O(1) で処理されます
• それ以外の場合、関数は再帰的に呼び出され、bが1減っていきます
• 再帰の深さは b に比例するため、全体で O(b) 時間がかかります
• 各再帰ステップでの計算は乗算のみなので O(1) です

空間計算量
この関数の空間計算量は O(b) です：

• 再帰呼び出しにより、コールスタックに最大 b 個の関数呼び出し情報が保存されます
• 各呼び出しでのローカル変数は定数個（a, b のみ）ですが、再帰の深さに比例してスタックの使用量が増加します

問15

次の関数の時間計算量と空間計算量はなんでしょうか。

def mod(a, b):
    if b == 0:
        return -1  # 0で割ることはできないのでエラー値を返す
    div = a // b   # 整数除算
    return a - div * b

回答・解説

時間計算量
このコードの時間計算量は O(1) です。

• 条件分岐（if文）は定数時間 O(1) で実行されます
• 整数除算（a // b）は一般的に基本演算として扱われ、定数時間 O(1) とみなします
• 減算と乗算も同様に定数時間 O(1) です
• これらの操作はすべて入力サイズに関係なく一定時間で実行されますなので O(1) です

空間計算量
この関数の空間計算量は O(1) です：

• 使用している変数は div のみで、入力サイズに関係なく一定のメモリしか使用しません
• 追加のデータ構造も使っていません

問16

次の関数の時間計算量と空間計算量はなんでしょうか。

def div(a, b):
    count = 0
    sum = b
    while sum <= a:
        sum += b
        count += 1
    return count

回答・解説

時間計算量
このコードの時間計算量は O(a/b) です。

• ループは sum が a より大きくなるまで実行されます
• 各ループでは sum に b を加算していきます
• 初期値は sum = b で、毎回 b ずつ増加するので、このループは約 a/b 回実行されます
• よって時間計算量は O(a/b) となります

空間計算量
この関数の空間計算量は O(1) です：

• 使用している変数は count と sum の2つのみで、入力サイズに関係なく一定のメモリしか使用しません
• 追加のデータ構造も使っていません

問17

次の関数は「整数値」の平方根を計算するものです。
時間計算量と空間計算量はなんでしょうか。

def sqrt(n):
    return sqrt_helper(n, 1, n)

def sqrt_helper(n, min, max):
    if max < min:
        return -1  # 平方根でない
    
    guess = (min + max) // 2  # 中間点を推測値とする
    
    if guess * guess == n:  # 完全な平方数の場合
        return guess
    elif guess * guess > n:  # 推測値が大きすぎる場合
        return sqrt_helper(n, min, guess - 1)  # より小さい値を探す
    else:  # 推測値が小さすぎる場合
        return sqrt_helper(n, guess + 1, max)  # より大きい値を探す

回答・解説

時間計算量
このコードの時間計算量は O(log n) です。

• 二分探索アルゴリズムを使用しており、各ステップで探索範囲が半分になります
• 初期探索範囲は 1 から n までなので、最大でも log₂(n) 回の再帰呼び出しが行われます
• 各再帰呼び出しでの計算（乗算や加算）は O(1) です
• よって全体の時間計算量は O(log n) となります

空間計算量
この関数の空間計算量は O(1) です：

• 再帰呼び出しごとにコールスタックに情報が保存されます
• 再帰の深さは最大 log₂(n) になるため、スタックの使用量は O(log n) です

問18

次の関数の時間計算量と空間計算量はなんでしょうか。
結果を問17と比較してみてください。

def sqrt(n):
    for guess in range(1, n + 1):
        if guess * guess == n:
            return guess
    return -1

回答・解説

時間計算量
このコードの時間計算量は O(√n) です。

• for ループは1から始めて順番に値を試し、guess * guess == n となる値を見つけるまで実行されます
• guess が√n に達すると guess * guess は n になるため、ループは最大で√n 回実行されます
• 各イテレーションでの乗算は定数時間 O(1) です
• よって全体の時間計算量は O(√n) となります

空間計算量
この関数の空間計算量は O(1) です：

• 使用している変数は guess のみであり、入力サイズに関係なく一定のメモリしか使用しません
• 追加のデータ構造も使っていません
• 再帰呼び出しもないため、スタック領域も一定です

問19

次の関数は、新たに大きいいサイズの配列を作り値を追加し、その配列を返します。
時間計算量と空間計算量はどうなるでしょうか。
また、この実装の効率性の問題を指摘し、実際の動的配列の実装における償却時間計算量を教えてください。

def copy_array(array):
    copy = []
    for value in array:
        copy = append_to_new(copy, value)
    return copy

def append_to_new(array, value):
    # すべての要素を新しい配列にコピー
    bigger = [0] * (len(array) + 1)
    for i in range(len(array)):
        bigger[i] = array[i]
    
    # 新しい要素を追加
    bigger[len(array)] = value
    return bigger

回答・解説

append_to_new 関数の計算量
時間計算量
append_to_new 関数の時間計算量は O(n) です。

• 新しい配列 bigger の作成は O(n+1) = O(n) です
• for ループは配列の長さ n 回実行され、各イテレーションは O(1) です
• よって全体で O(n) の時間計算量になります

空間計算量
空間計算量も O(n) です。

• 元の配列のサイズ+1の新しい配列を作成するため

copy_array 関数の計算量
時間計算量
copy_array 関数の時間計算量は O(n²) です。

• for ループは入力配列のサイズ n 回実行されます
• 各イテレーションで append_to_new を呼び出します
• 最初の呼び出しでは配列サイズは0、次は1、次は2...と増加します
• そのため、総時間計算量は 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²) となります

空間計算量
空間計算量は O(n) です。

• 最終的に返される配列のサイズは n です
• ただし、関数実行中に多数の一時的な配列が作成されますが、ガベージコレクションによって解放されます

アルゴリズムの説明
このコードは動的配列（例：JavaのArrayListやC#のList）の基本的な実装原理を示しています：

append_to_new 関数：

• 既存の配列より1要素大きい新しい配列を作成
• 元の配列のすべての要素をコピー
• 新しい要素を末尾に追加
• 新しい配列を返す

copy_array 関数：

• 空の配列から始める
• 入力配列の各要素に対して append_to_new を呼び出し
• 最終的にすべての要素を含むコピーを返す

効率性の問題
この実装は非効率的です。要素を1つ追加するたびに新しい配列を作成してコピーするため、n要素の配列を作るのに O(n²) の時間がかかります。
実際の動的配列の実装では、容量が足りなくなったときだけ再割り当てを行い、通常は現在のサイズの2倍のサイズで新しい配列を作成します。これにより、n要素の追加の償却時間計算量は O(n) に改善されます。
Pythonのリストは内部でこのような最適化された動的配列として実装されており、単純な append() メソッドを使用するだけで効率的に要素を追加できます。

Pythonのリストの内部構造

https://github.com/python/cpython/blob/main/Objects/listobject.c

1. 行127-128: "Add padding to make the allocated size multiple of 4. The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ..."
   （容量を4の倍数にし、成長パターンは 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... となる）
2. 行132: 実際の計算式は new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
   この式は：

• newsize（必要なサイズ）
• +（newsize >> 3）（必要なサイズの1/8を追加）
• +6（さらに6要素分の余裕）
• &~(size_t)3（4の倍数に切り上げ）

3. さらに、行133-137では、新しいサイズが古いサイズよりもっと大きな過剰割り当てになる場合は、過剰割り当てを減らす調整も行っています。

これを見ると、Pythonのリスト実装は以下のようになっています：

1. 構造体:

• PyObject**型の配列ポインタ（ob_item）
• 割り当てられたサイズ（allocated）
• 実際に使用されているサイズ（ob_size - PyObject_VAR_HEADマクロ内）

2. 成長戦略:

• 新しいサイズ = 必要なサイズ + (必要なサイズの1/8) + 6（余裕分）
• 4の倍数に丸める
• 特定の条件下で過剰割り当てを避ける最適化

3. 最適化:

• 既存の割り当てが十分なら再割り当てを避ける（allocated >= newsize && newsize >= (allocated >> 1)）
• つまり、縮小する場合でも割り当てられたサイズの半分以上になるなら再割り当てしない

問20

次の関数は、ある数の各位の値を足し合わせます。
時間計算量と空間計算量はどうなるでしょうか。

def sum_digits(n):
    sum = 0
    while n > 0:
        sum += n % 10  # nを10で割った余り（最下位の桁）を加算
        n //= 10       # nを10で割る（最下位の桁を削除）
    return sum

回答・解説

時間計算量
このコードの時間計算量は O(log n) です。

• while ループはnが0より大きい間続きます
• 各ループでnは10で割られます（n //= 10）
• n桁の数値の場合、ループは約log₁₀(n)回実行されます
  • 例：n = 1234（4桁）の場合、ループは4回実行されます

つまり、入力値nの桁数に比例した時間がかかります。桁数はlog₁₀(n)に比例するため、時間計算量はO(log n)となります。

空間計算量
この関数の空間計算量は O(1) です：

• 使用する変数はsumと入力nのみです
• 入力サイズに関係なく、使用するメモリ量は一定です

問21

次の関数は、長さkの文字列の中で、文字がそーとされたものをすべて表示します。
時間計算量と空間計算量はなんでしょうか。

def ith_letter(i):
    return chr(ord('a') + i)

def is_in_order(s):
    for i in range(1, len(s)):
        prev = ord(s[i-1])
        curr = ord(s[i])
        if prev > curr:
            return False
    return True

def print_sorted_strings(remaining, prefix=""):
    if remaining == 0:
        if is_in_order(prefix):
            print(prefix)
    else:
        for i in range(26):
            c = ith_letter(i)
            print_sorted_strings(remaining - 1, prefix + c)

num_chars = 26

回答・解説

時間計算量
このコードの時間計算量は O(k × c^k) または O(k × 26^k) です。

• 文字列生成: すべての可能な長さ k の文字列を生成するには O(c^k) の時間がかかります。再帰ツリーの各レベルで c 個の分岐があり、深さが k なので。
• ソート順チェック: is_in_order 関数は文字列を1文字ずつ比較するため O(k) の時間がかかります。
• 組み合わせた時間計算量: 各生成された文字列に対してソート順チェックを行うため、総時間計算量は O(k × c^k) となります。

したがって、正確な時間計算量は O(k × c^k) または、本問題では O(k × 26^k) です。

空間計算量
この関数の空間計算量は O(k) です：

• 再帰スタック: 再帰の深さは k なので、スタックには O(k) のスペースが必要です。
• 文字列のスペース: 各再帰レベルでは、最大長 k の文字列 prefix が保持されます。

問22

次の関数は、2つの配列について共通する値を数えるものです。
2つの配列は全く同じものではないと仮定します。
片方の配列bをソートして、もう1つの配列aの要素を順に、配列bに含まれるかどうかを二分探索を用いて調べます。
時間計算量と空間計算量はどうなるでしょうか。

def intersection(a, b):
    # 配列bをソートする（mergesort()に相当する前処理）
    b.sort()
    
    intersect = 0
    
    # 配列aの各要素について
    for x in a:
        # 二分探索でxがbに含まれるかチェック
        if binary_search(b, x) >= 0:
            intersect += 1
    
    return intersect

# 二分探索の実装
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

回答・解説

時間計算量
このコードの時間計算量は O(m log m + n log m) です。
ここで、mは配列bの長さ、nは配列aの各要素です。

1. ソート操作: 配列bをソートするのに O(m log m) の時間がかかります
2. ループと二分探索:

• 配列aの各要素（nとします）に対して二分探索を行います
• 二分探索は O(log m) の時間がかかります
• したがって、このループ全体では O(n log m) の時間がかかります

全体の時間計算量は:
O(m log m + n log m)
これは以下のように簡略化できます：

• m > n の場合: O(m log m)（ソートが支配的）
• n > m の場合: O(n log m)（ループが支配的）

一般的には O(max(m log m, n log m)) と表現できます。

空間計算量
このコードの空間計算量は 入力配列を含めると O(n+m) 含めないと O(1) です：

• 入力配列: 入力配列a, bのための空間 O(n + m)
• ソート: 使用するソートアルゴリズムによっては追加の空間が必要かもしれませんが、多くの言語の組み込みソートは元の配列を変更するため、追加の空間は必要ありません
• 変数: intersect, loop変数などに定数の空間のみ必要