[アルゴリズム]2週目2回目の運転時

3337 ワード
アルゴリズム#アルゴリズム# コンピュータ工学部 テキストリンク

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



    zerologのencoderについて話します
    C#Socket接続によるデータの送受信