入力のサイズとした関数の集合で表します。定数倍で抑えられることを意味します。この表記は問題の各入力サイズに対して、そのサイズの任意のインスタンスを解くために必要な"最大"の演算回数を見積もります。ここで、インスタンスとは問題の全ての入力値に具体的な値を設定したものを言います。問題が与えられるときには必ず入力の上限が定義されます。いくつか例を挙げます。与えられたx個のデータを、Aというアルゴリズムで整列する。xの最大値はnとする。この問題に対するAの効率はO(n2)である。Aは最悪でn2の計算ステップが必要である。x個の交差点とy個の道から成る地図情報を基に、交差点aから交差点bまでの最短距離をBというアルゴリズムで求める。xの最大値はn、yの最大値はmである。この問題に対するBの効率はO(mlogn)である。mlognの計算ステップが必要である。)の引数はある関数となります。)を「オーダーがnである」と言います。アルゴリズムの評価に関する典型的な関数について、実際の入力値nとその計算量を以下の表で見てみましょう。ここでlogは2を底とする対数関数です。19000000どの関数がどれだけ効率が良いか、または悪いかを考えてみましょう。オーダーがO(logn)、O(n)、O(nlogn)のアルゴリズムは効率が良いと言えます。nが増加しても計算量はさほど増加しません。逆に、オーダーがO(2n)やO(n!)のアルゴリズムは、入力nが数十になっただけで、計算量が何千桁にも至ってしまいます。地球上最速のコンピュータを使っても、数百年かかってしまうであろう計算量です。これらの効率の悪いオーダーは、総当りなどの、素朴で力任せのアルゴリズムに良く見られます。初心者のプログラマがよくはまってしまいます。世の中には未解決の問題も多々あり、それらを解くことのできる最速のアルゴリズムのオーダーがO(2n)である場合もあります。重要なことは、プログラムを実装する前に、入力の上限から自分のアルゴリズムの最悪計算ステップを評価することです。これは、学習するよりも、難しい問題にチャレンジし、失敗を繰り返すことによって経験することができます。現在のコンピュータは膨大な計算を一瞬でこなすことができますが、すべての問題を高速に解決できるわけではありません。膨大な量のデータを高速に計算する優れたプログラムを書くためには、問題の性質を十分に考慮し効率の良いアルゴリズムを考える必要があります。アルゴリズムの効率とは与えられた問題を解くためのアルゴリズムを考えるとき、そのアルゴリズムの効率を評価する「ものさし」が必要になります。アルゴリズムを考えてプログラムを実装するときには、まずその効率を測り、そのアルゴリズムの効率が与えられた問題を解くのに十分かどうかを確認する必要があります。この過程を無視すると、実装されたプログラムは使い物にならなかった、という失敗をしてしまいます。効率の良いアルゴリズムに求められるものは、処理するデータの数が増加しても計算ステップ数が爆発的に(指数的に)増加しないという性質です。入力値によっては計算ステップ数が爆発的に増加し、事実上処理がストップしてしまうようなプログラムは使い物になりません。あるアルゴリズムがデータを100個処理するのに1秒しかかからなくても、データを10000個に増やすと数時間もかかる場合があります。アルゴリズムを実装したときに100個の入力データでテストし満足する結果が得られたとしても、実際にそのプログラムを使う人は10000個のデータを処理する必要があるかもしれません。コンピュータの処理能力は日々進歩していますが、処理するデータの量や処理の複雑さも日々増しています。コンピュータの計算能力が余っていれば使ってしまいたくなるのが人情です。後々まで通用する効率の良いアルゴリズムを追求しなければなりません。アルゴリズム主に以下の2つの計算量で評価されます。complexity)プログラムの実行に必要な時間を評価します。complexity)プログラムの実行に必要な記憶領域で評価します。時間計算量がよく用いられますが、どちらの評価が重要ということはなく、これらのバランスを考えてアルゴリズムを考えることが重要です。この効率の概念を無視してしまったら、これから学ぶアルゴリズムの意義も半減してしまいます。masimarock。