Chap01. Analyzing Algorithms and Promblems: Principles and Examples

Anylyzing Algorithms and Problems

アルゴリズムの原因を分析する:複数のアルゴリズムからどのアルゴリズム(ユーザー)を選択するか、または既存のアルゴリズムを改善するかを決定する(研究開発)

Correctness

Input(precondition)をoutput(postcondition)に変換する操作(演算子)/命令(コマンド)/文(ステップ)
inputが条件/アルゴリズムを満たす場合/outputは条件を満たさなければならない

Amount of work done

-ワークロードの測定時に効率を測定できる
-コンピュータ、言語、プログラマーによって異なります.
-主にinputsizeに依存
-基本操作を選択してクリーンアップn

Worst-Case Complexity

t(I)はbasic操作の数である

Average Complexity

pr(I)は、I発生確率を入力する統計値または仮定である
Example::Search in an Unordered Array

int seqSearch(int[] E, int n, int K)
int ans, index;
ans = -1; // Assume failure.
for (index = 0; index < n; index++)
	if (K == E[index])
		ans = index; // Success!
		break; // Done!
return ans;

Space Usage and Simplicity

空間がinputによって決定されると,最悪の場合と平均的な場合の解析が可能になる.
ほとんどの場合、TimeとSpace Tradeoff

は簡潔性が良い
-アルゴリズムの正確性の証明が容易
-

プログラムの作成、デバッグ、および変更

最適

すべての問題に固有の複雑さがあります.最小ワークロードが決定されました.
「問題を解決するにはどのくらいの演算が必要ですか」
最適化は,既知+将来開発されるアルゴリズムにおいて最適な状態にあることを意味する.