2011 コンピュータソフトウェア試験プログラマー: アルゴリズム分析の基礎学習

コンピュータの問題解決のプロセスにおいて、データ構造とアルゴリズムはプログラムの 2 つの主要要素であり、互いに補完し合い、不可欠です。アルゴリズムとデータ構造の品質は直接関係しています。データ構造の品質は、さまざまな操作を実装するアルゴリズムに反映されます。データ構造の分析は、本質的にはさまざまな操作を実装するアルゴリズムの分析です。アルゴリズム分析は複雑な問題であり、まずは優秀性の基準を決定する必要があります。アルゴリズムの品質を判断する基準はいくつかあります。

（１）正確性指定された機能を正しく実行するにはアルゴリズムが必要です。これは最も重要かつ基本的な原則です。

（２）使いやすさアルゴリズムは読みやすい、つまり簡単に読めるものでなければなりません。この要件を満たすには、アルゴリズムのロジックが明確で、単純かつ構造化されている必要があります。

（３）堅牢性アルゴリズムには、優れたフォールト トレランス、つまり例外処理を提供し、不合理なデータをチェックでき、異常な中断やクラッシュが頻繁に発生しないことが求められます。

（４）効率性アルゴリズムの効率とは、主に、アルゴリズムの実行時に消費されるコンピュータ リソース (ストレージや実行時のオーバーヘッドなど) のことです。前者はアルゴリズムのスペース コストと呼ばれ、後者はアルゴリズムの時間コストと呼ばれます。

時間コストは一般的に使用される評価指標であり、多くの場合、時間の複雑さによって測定されます。アルゴリズムがプログラムに変換され、コンピューター上で実行される場合、実行にかかる時間は常に次の要因によって決まります。

ハードウェアの速度。 CPU 速度とデータ アクセス速度が速いほど、プログラムの実行時間は短くなります。

選択されたプログラミング言語。プログラミング言語のレベルが高くなるほど、実行効率は低くなります。たとえば、アセンブリ言語プログラムの実行効率は、高水準アルゴリズム言語よりも高いことがよくあります。

コンパイラによって生成されたオブジェクト コードの品質。コードの最適化が優れたコンパイラの場合、生成されるプログラムの品質は高くなります。たとえば、コード効率が最適化された C 言語プログラムは、最適化されていないコードよりも効率的です。

問題の規模。明らかに、大規模な問題に対する問題解決プロセスは、小規模な問題に対する問題解決プロセスよりも時間がかかります。

当然のことながら、さまざまな要因が不確実な場合、アルゴリズムの実行時間を比較することは困難です。つまり、アルゴリズムの実行にかかる絶対時間を使用してその効率を測定するのは不適切です。この目的のために、上記のさまざまなコンピュータ関連のソフトウェアおよびハードウェア要因は、特定のアルゴリズムを実行するために必要な作業量が問題のサイズのみに依存するように、または問題のサイズの関数になるように決定できます。一方、アルゴリズムの長所と短所を総合的に評価するには、アルゴリズムの時間消費だけでなくメモリ消費も考慮する必要があります。特に大規模な問題の場合、スペース消費の分析は不可欠です。したがって、時間と空間に基づいたアルゴリズム分析、つまりアルゴリズムの時間計算量分析と空間計算量分析があります。