実行時間のオーダーの表記法
関数fがあったときに、
すべての場合において、入力のサイズnに比例して実行時間が変化する場合
実行時間は
f(n) = Θ(n)
と表される。
入力の中身によってはオーダーに差がでるとき、
これ以上は実行時間が大きくならないオーダーがnであれば
f(n) = Ω(n)
と表し、
これ以上は実行時間が小さくならないオーダーがnであれば
f(n) = O(n)
と表す。
関数fがあったときに、
すべての場合において、入力のサイズnに比例して実行時間が変化する場合
実行時間は
f(n) = Θ(n)
と表される。
入力の中身によってはオーダーに差がでるとき、
これ以上は実行時間が大きくならないオーダーがnであれば
f(n) = Ω(n)
と表し、
これ以上は実行時間が小さくならないオーダーがnであれば
f(n) = O(n)
と表す。