計算量とO記法（オーダ記法）とは？けいさんりょうとおーきほう
計算量とO記法（オーダ記法）とは、入力サイズnが増えたときに実行時間や必要記憶量がどう増えるかを、支配的な項だけ残して表したもの。O記法では係数と低次項を落とすため、載せる石やコンパイラに依らず増え方だけを比べられる。組込みでは平均ではなく最悪計算量が、周期処理が締切に間に合うかどうかの見積りの起点になる。
最終更新：2026-10-06
エンベデッドSPを最短で暗記・合格する →背景
実測値は搭載したコアとコンパイラの最適化で変わるので、方式を選ぶ段階では比較の物差しにならない。そこで係数を捨てて増え方だけを残す表記が要る。ただしオーダは定数を捨てる表記なので、それだけでは「このMCUで何マイクロ秒か」は出ない。実務ではオーダで候補を絞り、最悪計算量に実測の1回あたりコストを掛けて最悪実行時間へ落とし、割込み周期やタスクの周期と突き合わせる二段構えで使う。この二段目を踏まないと、机上で速いはずの方式が実機で締切を割る。
具体例
64点の周波数解析を考える。定義どおりの離散フーリエ変換はO(n²)で複素乗算が約4,096回、高速フーリエ変換はO(n log n)で(64÷2)×6＝192回まで落ちる。1回の複素乗算に10クロックかかる100MHzのコアなら前者が約410マイクロ秒、後者が約19マイクロ秒で、1kHz周期の制御ループに載るかどうかがここで決まる。
試験での引っ掛け
O記法は増え方の傾向であって、実行時間の大小そのものを示すものではない。nが小さければ単純なO(n²)の実装のほうがO(n log n)より速いことがあり、定数の大きい再帰はスタック消費の面でも組込みでは不利になる。時間計算量と空間計算量の混同も定番で、RAMが数十キロバイトの機種では空間側が先に効く。係数と定数項は無視するので、O(2n)もO(n+5)もどちらもO(n)と書く点も見落としやすい。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。