最近学んだこと...計算量ってなんじゃらほい？

はじめに

本記事は、G'sACADEMY Advent Calender2024に寄せて投稿した記事となります！

メリクリ！！プログラミング初心者の元メガネ屋さんです。
G'sACADEMY Advent Calenderということで、「こういうの作ったよ～」とか面白い記事を書こうと思ってたのですが...色々とバタバタしていて取り組めなかったので、最近自分が知ったことをアウトプットで勘弁いただければと思います。

今回アウトプットするのは「計算量とO記法」についてです。
自分のようなプログラミング初心者は、正直プログラミングを動かすのに手一杯で中々考えが及ばない内容ではあるのですが...とても大切な考え方だと思ったので、プログラミング初心者の同志にむけてアウトプットできればと思います。

計算量とO記法について

計算量とは

プログラムの処理（＝アルゴリズム）を評価するための指標のこと。
評価軸について主に2つの考え方がある。

• 時間計算量：処理を行うのにかかる時間（≒処理のステップの回数）を評価指標にする
• 空間計算量：処理を行うのに必要なメモリの容量を評価指標にする

なぜプログラムの処理を評価する必要があるのでしょうか。それはパフォーマンス（処理の速さ）に影響してくるからです。プログラムの処理が複雑になったり、扱うデータ量が増えてくるほど、プログラムの処理の組み方がパフォーマンスに大きく影響するようになります。

O記法とは

O記法は、時間計算量について、計算量の概算を得るためのものです。
「入力されるデータのサイズに対して、実行時間の増加する割合」を表したもので、ざっくばらんに言うならば「入力値に対して、処理のステップが大体何回生じるか」を記述したものという感じです。

ではO記法は、どのように記述するのか。
書き方は、非常にシンプルで、下記３つに従って記述するだけです。

1. 「O(処理の回数)」と記述する
2. 処理の回数は、一番大きい項以外無視して記述する
3. 処理の回数は、定数倍の定数は無視して記述する

実際に、下記コードを例に見ていきましょう。

/*==========
入力値 n が与えられたとき、1からｎまでの総和を求める
==========*/
function calculateNumber(n){
    //処理のステップ１回
    let total = 0; 
    //処理のステップn回 
    for(let i=1; i <= n; i++){
        total += i;
    }
    //処理のステップ１回
    return total;
}

関数calculateNumberで実行される処理の回数は n+2 回。
「 処理の回数は一番大きい項以外無視して記述する」ことになるので、計算量はO(n)と記述することができます。

なぜ計算量を意識することが大切か

同じ結果を得るための処理であっても、プログラムの処理の組み方でパフォーマンスが大きく変わります。実際に下記問題を例に、２つのコードの計算量を比較してみます。

◆問題文

配列arrayについて、配列の長さを表すnと、配列の要素としてn個の数値、またn>kになるような部分配列の長さk、を入力値として与える。この時、配列arrayから、長さがkとなる全ての部分配列を取り出し、それぞれの部分配列の要素の和を計算して、リスト形式で出力してください。

/*==========
具体例：
#入力値
配列arrayの長さ n = 5
部分配列の長さ k = 3
配列arrayの要素 = [1, 2, 3, 4, 5]

※入力値はn,k,[配列arrayの要素]の順で与えられる

#出力値
[6,9,12]
==========*/

◆非効率な計算方法のコード例

計算量：O(nk)

• 部分配列の和を求める（内側のループ処理）→Ｏ(k)
• 取りうる全ての部分配列で処理を実行（外側のループ処理）→Ｏ(n)

→外側のループ処理の回数分、内側のループ処理を行っているので O(nk)

const reader = require("readerline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

let lines = [];

reader.on("line", (line) => {
  lines.push(line);
});

reader.on("close", () => {
   const conditions = lines[0];
    const [n,k] = conditions.split(/\s/,2).map(e=>parseInt(e));
    const array = lines[1].split(/\s/).map(e=>parseInt(e));
    
    const result = [];
    
    // すべての部分配列で処理を行う（外側のループ）
    for(let i = 0; i <= n-k; i++){
        let count = 0;
        //部分配列の和を求める(内側のループ)
        for(let j = 0; j < k; j++){
            count += array[i+j];
        }
        result.push(count);
    }
    
    console.log(result);

  }
});

◆効率的な計算方法のコード例

計算量：O(n)

• array[0]...array[k]の部分配列の和を計算 → O(k)
• 部分配列の参照範囲をずらし、ずれた差分を計算する形で、すべての部分配列の場合を計算→Ｏ(n-k)

→ O(k)+O(n−k) 、またの n>k なので k の項は簡略化＝O(n)

const reader = require("readerline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

let lines = [];

reader.on("line", (line) => {
  lines.push(line);
});

reader.on("close", () => {
  const conditions = lines[0];
  const [n, k] = conditions.split(/\s/).map((e) => Number(e));
  const array = lines[1].split(/\s/).map((e) => Number(e));

  let result = [];
  let count = 0;

  // array[0]...array[k]の部分配列の和を計算
  for (let i = 0; i < k; i++) {
    count += array[i];
  }
  result.push(count);

  //部分配列の参照範囲をずらし、ずれた差分を計算
  for(let i = 0; i < n-k; i++){
    count = count-array[i]+array[i+k];
    result.push(count);
  }
  
  console.log(result);
});

まとめ

ここまでウダウダ書いてきましたが...伝えたかったことは、プログラミングの処理の組み方によってパフォーマンスが大きく変わるので、ただ「動けばいい」だけでなく「効率的に動かす」ことを意識してコードを書くことが大切だということ。
最近知って、とても勉強になったので、ぜひ自分と同じ初学者の方にも共有したく、本記事を書いた次第であります。

本記事内容に誤りなどありましたら、ご指摘賜れますと幸いです！

参考文献：

• プログラムの計算量、オーダー表記 O( ) の求め方のまとめ
• [初心者向け] プログラムの計算量を求める方法
• 実践力をアップする Pythonによるアルゴリズムの教科書

余談

最近色々言い訳を作ってはコードを書けていない気がする...猛省。
やっぱ「Cool, Geek, Act with Passion」であらないといけないよね！！

...とかウダウダ抜かしてたら、どこぞの兄貴に
「心の中で思ったならッ!その時スデに行動は終わっているんだッ!」
って怒られそうな気がしてきたので、コード書こ。