アルゴリズム解析（アルゴリズムかいせき）とは、アルゴリズムの実行に必要とされるリソース（時間や記憶領域）量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数（時間複雑性）や記憶領域サイズ（空間複雑性）への関数として表される。

アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。

アルゴリズム解析ではふつう、漸近的（asymptotic）な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。例えば、二分探索のステップ数は入力サイズの対数に比例し、これを O(log(n)) と表記したり、「対数時間」と称したりする。このような漸近的な見積もりを用いるのは、同じアルゴリズムでも実装の違いにより差が出るのを捨象するためである。異なる妥当な実装による効率の違いは定数倍に留まる。この定数を隠れた定数（hidden constant）と呼ぶ。

漸近的でない正確な効率がわかる場合もあるが、そのためには「計算モデル」と呼ばれるアルゴリズムの特定の実装を仮定する必要がある。計算モデルはチューリング機械のような抽象化された機械を使うか、個々の命令の実行時間が変化しないと仮定することが多い（例えば実際のコンピュータではキャッシュにヒットするかしないかでは大きく実行時間が異なるが、アルゴリズム解析では一般にそれを無視する）。例えば、二分探索で N 個のソートされた数から探索する場合、1回の参照を一定の単位時間でできるとした場合、回答を得るまでに最大で log2 N+1 単位時間を要する。
コストモデル

時間効率の見積もりはステップとして定義するものに依存する。意味のある解析をするには、各ステップの実行時間の上限が一定でなければならない。例えば、2つの数の加算を1ステップと仮定したとしよう。この仮定は場合によっては正しくない。例えば数が極めて大きくなれば、加算が一定時間で完了するとは限らないからである（紙と鉛筆で2桁の加算をする場合と1000桁の加算をする場合を比べていただきたい）。

一般に次の2つのコストモデルが使われる[1][2][3][4][5]。
一様コストモデル
マシンによる全ての演算について、一定のコストを割り当てる。数値の大きさは考慮しない。
対数コストモデル
マシンによる全ての演算について、計算対象となる数値のビット数に比例したコストを割り当てる。

後者の方がより複雑になるので、任意精度演算アルゴリズムなどそれが必要となる場合でしか使用されない。任意精度演算は例えば暗号理論で必要とされる。

見過ごされがちな重要な観点として、公表されている問題の下限（最良実行時間）は実際のコンピュータよりも制限された計算モデルについてのものであることが多いという点が挙げられる。そのため、実際にアルゴリズムを実装し実行してみると、想定していたよりも実行時間が短くなる（成長が遅い）ことがある[6]。
実行時間解析

実行時間解析とは、アルゴリズムの入力サイズ（通常 n と記される）が増大したときの実行時間の増大を評価し推定することで、アルゴリズムを理論的に分類することである。実行時間効率は計算機科学の重要な関心事である。プログラムが完了するまでに数秒で済むのか、数時間かかるのか、1年以上かかるのかは、実装したアルゴリズムに依存する（アルゴリズムの実行時間を実測して解析するのは性能解析と呼ばれる）。
実測の問題点

アルゴリズムはプラットフォームに依存しない（すなわち、アルゴリズムは任意のオペレーティングシステムが動作する任意のコンピュータ上で任意のプログラミング言語で実装できる）ので、複数のアルゴリズムの性能を比較するのに経験的技法（実測値）を用いるのはあまりにも問題が多い。

例として、大きさ n のソートされたリストから特定のエントリを検索するプログラムを考える。そして、最新型の高性能なコンピュータAでは線型探索アルゴリズムでプログラムを実装し、古い低性能なコンピュータBでは二分探索アルゴリズムでプログラムを実装したとする。それら2つのコンピュータでそれぞれのプログラムのベンチマークテストを実施し、次のような結果が得られたとする。

n（リストの大きさ）コンピュータAの実行時間
（ナノ秒単位）コンピュータBの実行時間
（ナノ秒単位）
157100,000
6532150,000
250125200,000
1,000500250,000

この測定結果を見ると、コンピュータAで実行したアルゴリズムの方がコンピュータBのそれよりも遥かに高速だと結論しそうになる。しかし、入力リストの大きさを十分大きくすると、その結論は全くの間違いだったことが判明する。

n（リストの大きさ）コンピュータAの実行時間
（ナノ秒単位）コンピュータBの実行時間
（ナノ秒単位）
157100,000
6532150,000
250125200,000
1,000500250,000
.........
1,000,000500,000500,000
4,000,0002,000,000550,000
16,000,0008,000,000600,000
.........
63,072 × 101231,536 × 1012 ナノ秒、
または1年1,375,000 ナノ秒,
または 1.375 ミリ秒

線型探索プログラムを実行したコンピュータAでの成長率（実行時間の増加率）は線型性を示す。すなわち、そのプログラムの実行時間は入力サイズに比例している。入力サイズが2倍になれば実行時間も2倍になり、入力サイズが4倍になれば実行時間も4倍になる、という具合である。一方コンピュータBでは二分探索プログラムを実行したので、成長率は対数的になる。入力サイズが2倍になったとき、実行時間の増加は一定である（この例では25,000ナノ秒）。表面上コンピュータAの方が高速でも、コンピュータBの方が成長率が低い（遅い）ので、入力サイズが大きくなれば必然的にコンピュータBの方が勝つことになる。
成長のオーダー詳細は「ランダウの記号」を参照

大まかに言えば、あるアルゴリズムの入力サイズ n がある特定の値を超えたとき、その成長率がある数学関数のオーダーであるとは、その関数 f(n) に正の定数をかけた値がそのアルゴリズムの実行時間の上限（英語版）を与えることを意味する。