アルゴリズム解析(アルゴリズムかいせき)とは、アルゴリズムの実行に必要とされるリソース(時間や記憶領域)量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数(時間複雑性)や記憶領域サイズ(空間複雑性)への関数として表される。アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。コストモデル.後者の方がより複雑になるので、任意精度演算アルゴリズムなどそれが必要となる場合でしか使用されない。任意精度演算は例えば暗号理論で必要とされる。見過ごされがちな重要な観点として、公表されている問題の下限(最良実行時間)は実際のコンピュータよりも制限された計算モデルについてのものであることが多いという点が挙げられる。そのため、実際にアルゴリズムを実装し実行してみると、想定していたよりも実行時間が短くなる(成長が遅い)ことがある。実行時間解析.実測の問題点.アルゴリズムはプラットフォームに依存しない(すなわち、アルゴリズムは任意のオペレーティングシステムが動作する任意のコンピュータ上で任意のプログラミング言語で実装できる)ので、複数のアルゴリズムの性能を比較するのに経験的技法(実測値)を用いるのはあまりにも問題が多い。成長のオーダー.経験的な成長のオーダー.実行時間複雑性の評価.与えられたアルゴリズムの最悪ケースの実行時間複雑性は、そのアルゴリズムの構造を調べ、いくつかの単純化仮定をすることで評価できることがある。次の擬似コードを見てみよう。要するに、内側ループの本体にかかる時間は、次のような等差数列で表される。この式は次のように因数分解できる。内側のループの条件部にかかる時間の総計も同様に次のように得られる。これを因数分解すると次のようになる。以上からこのアルゴリズムにかかる時間の総和は次のようになる。これを整理すると次のようになる。他のリソースの成長率解析.