アルゴリズムの実行時間

＜実行時間を表すO記法＞

オーダ

　どれくらい計算に時間がかかるかを表す

O記法

　オーダによってアルゴリズムを表す記述方法。

　O記法では、データの個数をnとし、それに対する計算量をO(n)で表す。

　O(n)は、データの個数が２倍、３倍になると、計算量も２倍、３倍になると言うこと。O(n^2)は、データの個数が２倍、３倍になると、計算量は４倍、９倍になると言うことを表す。

　O記法では、大量のデータを扱う場合を考えるため定数や係数は無視する。

＜探索アルゴリズムの実行時間＞

　ハッシュ探索法では、衝突が起きない限り、原則１回の比較でデータを見つけることができるため、データ個数にかかわらず0(1)となる。

　線形探索法は、最大でデータ個数の分だけ比較することになるため、データが多い場合には最も遅いアルゴリズムとなる。

・ハッシュ探索法のオーダ：O(1)

・２分探索法のオーダ：O(log2n)

・線形探索法のオーダ：O(n)

＜整列アルゴリズムの実行時間＞

　交換法（バブルソート）、挿入法、選択法の実行時間（オーダ）は全てO(n^2)となる。