並列アルゴリズム
逐次アルゴリズムの計算量は使用する領域(メモリ)と時間(プロセッササイクル)で測る。並列アルゴリズムではもう1つの観点として、プロセッサ間の通信コストを考慮しなければならない。並列プロセッサの通信には、共有メモリを使う方法とメッセージパッシングによる方法がある。
共有メモリ処理では、データのロックが必要となり、オーバーヘッドを生じる。また、アルゴリズムの一部が逐次化されてしまう。
メッセージパッシング処理では、バス上をメッセージ転送するオーバーヘッドを生じ、キューやメッセージボックスのためのメモリも必要になり、キューイングすることでメッセージにレイテンシが生じる。クロスバースイッチのような特殊なバスを使うことで、プロセッサ間の通信オーバーヘッドを低減させることができるが、通信量は個々の並列アルゴリズムによって異なる。
もう1つ、並列アルゴリズムには負荷分散がうまく行われるかという問題がある。例えば、ある範囲の数が素数かどうかを調べる場合、割り当てが不公平だと一部のプロセッサが早めに処理を終えてしまい、何もしていない状態になる。
並列アルゴリズムの一種として分散アルゴリズムがある。分散アルゴリズムは、コンピュータ・クラスターや分散コンピューティング環境で動作するよう設計されており、古典的な並列アルゴリズムとは違った問題に対処する必要がある。