Chap01. Analyzing Algorithms and Promblems: Principles and Examples

Anylyzing Algorithms and Problems

How to Show an Algorithm is Optimal

-上記の場合、最悪の場合を最適とする
-両者が異なる場合、より効率的なアルゴリズムまたはより良い問題の複雑さがある
*注:アルゴリズムの複雑度は上限、問題の複雑度は下限
Examples::Devise A
ソートされていないシナリオで最低価格を検索

int findMax(int[] E, int n) 
{
int max;
max = E[0]; // Assume the first is max.
for (index = 1; index < n; index++)
/*l4*/	if (max < E[index])
		max = E[index];
return max;
}

基本操作比較(l 4),n-1回
Worst-Case Analysis
F(n)を探せ!

Class of Algorithms
- compare
- copy

F(n)証明
-すべてのentry値が異なると仮定
-n-1エントリはmaximalではありません.すなわち、各エントリには少なくとも1回の比較演算が必要です.
したがって、F(n)=n-1
-ベスト

は、Worst-CaseとF(n)が同じであるため

Classifying Functions by Their Asymptotic Growth Rates

Classifying Functions

big-omegaofg:成長率が等しいか速い関数の集合
big-theta of g:成長率が同じ関数の集合
big-oh of g:(関数gに対する成長率)成長率が等しいか小さい関数の集合

Thes Sets big-omega, big-theta, big-omega

2つの関数fおよびgは、実数関数、正常数cおよび正の整数n 0に対してである

Comparing Asymptotic Growth Rates

関数f(n)とg(n)におけるn無限大の比較

*littleは同じ成長率を含まない

Asymptotic Growth Rates