大話データ構造読書2-アルゴリズム

1、アルゴリズム:特定の問題を解決するためのステップの説明.コンピュータにおいて命令の秩序化シーケンスとして表現され、各命令は1つ以上の操作を表す.
アルゴリズムの5つの基本特性(入力、出力、貧乏性、確定性、実行可能性):
1)入力出力:0個以上の入力があり、少なくとも1個の出力がある.
2)無限性:アルゴリズムは、限られたステップを実行した後、無線ループが発生することなく自動的に終了し、各ステップは許容時間内に完了する.
3)確定性-各ステップは確定的な意味を持ち、二義性は現れない.
4)各ステップは実行可能でなければならない.すなわち、各ステップは限られた回数で実行可能である.
2、アルゴリズム設計の要求:
(1)正確性——アルゴリズムは少なくとも入力、出力、加工処理の曖昧性がなく、問題の需要を正確に反映し、問題の正確な答えを得ることができるべきである.(文法、適法入力データが要求を満たす出力結果、不正入力データが仕様説明を満たす要求、テストデータが要求を満たす出力結果)
(2)可読性
(3)頑丈性(入力データが不正な場合はアルゴリズムによる処理)
(4)イベント効率が高く(実行時間)、ストレージ量が低い
3、アルゴリズムの効率:
1+2+3+を求めます......+100=?,次の2つのアルゴリズムがあります.

int i, sum = 0, n = 100;
	for(i = 1; i <= n; i++){
	    sum = sum + i;
	}
	printf("%d",sum);

int sum = 0, n = 100;
	sum = (1 + n) * n / 2;
	printf("%d", sum);

第1セグメントは2 n+3回,第2セグメントは3回実行され,第2セグメントの効率は第1セグメントよりはるかに高いことがわかる.
4、1つのアルゴリズムの効率を判断する時、関数の中の定数とその他の副次的な項はよく無視することができて、更に主項の次数に注目すべきです.
時間の複雑さ:
大きなO段階にプッシュする方法:
    1.運転時間中のすべての加算定数を定数1で置き換える
    2.変更後の実行回数関数では、最上位レベルのみが保持されます.
    3.最上位次項が存在して1でない場合,この項に乗じた定数を除いて,大きなO次が得られる.
(1)定数次数,O(1)

int sum = 0, n = 100;//  
sum = (1 + n) * n / 2;//  
printf("%d", sum);//  

上は全部で3回実行しましたが、定数がいくらであれ、何基かのO(1)に注意してください.
(2)線形次数、キー分析循環構造の運行状況

int i;
for(i=0;i<n;i++){
    //      O(1)       
}

(3)対数次

int count = 1;
while(count < 1){
    count = count * 2;
    //      O(1)       
}

countごとに2を乗じると距離nがより近くなり、2^x=nはx=log 2 nを得るので、イベント複雑度はO(logn)である
(4)平方階

int i,j;
for(i=0;i<n;i++){
    for(j=i;j<n;j++){
        //      O(1)       
    }
}

i=0のとき、内循環はn回である.i=1,n-1回実行;......i=n-1は1回実行する.したがってn+(n-1)+(n-2)+......+1=n^2/2+n/2であり,時間的複雑度はO(n^2)である.
5、O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
6、一般的に特別な説明がない場合、最悪の時間の複雑さを指す.