アルゴリズム(1)

アルゴリズム#アルゴリズム#
1、アルゴリズムの評価指標－時間複雑度時間複雑度:アルゴリズムフロー中、最悪定数操作数の指標をOで表し、big O某某と読む.定数操作数を算出する式では、n^2であれば、nまたは定数(低次)[定数操作:1つの操作はデータ量に関係なく、毎回一定時間で完了する操作であり、定数操作と呼ばれる.]I、1つの秩序あるシーケンスの中である数値解決方法を検索する:二分法時間複雑度O(nlog n)II、1つの秩序あるシーケンス(list 1)の中で別のシーケンス(list 2)に存在しない数値を検索して解決方法を印刷する:まずlist 2をソートする;2つのシーケンスに対してそれぞれ1つの頭部を指すポインタp 1,p 2を設定し、2つの値を比較し、p 1>p 2の場合、p 2++;p 1=p 2の場合、p 1++、p 2++;p 1時間複雑度O(M+N)IIIの場合、1つのシーケンスをソートする解決方法:高速ソート時間複雑度O(nolgn)
題目:整然としたlist 1の中(n個の数)list 2の中(m個の数)の存在しない数を探して印刷解決方法を行います1:list 1の中のすべての数はlist 2の中のすべての数と比較して、時間の複雑度はO(mn)解決方法です2:list 1の中の数はすべて二分の方式を通じてlist 2の中のすべての数と比較して、時間複雑度はO(mlogn)解決策3:まずlist 2でソート操作を行い、その後、2つのシーケンスにそれぞれ1つの頭部を指すポインタp 1,p 2を設定し、2つの値を比較し、p 1>p 2の場合、p 2++;p 1=p 2の場合、p 1++、p 2++;p 1
2、ソートバブルソート時間複雑度O(n^2)余分空間複雑度O(1)7 5 4 3 6 2 1 0(0から1つの比較を開始し、毎回1つの数列の最大値を取得し、最後までバブルする;ソートが完了するまで)第1ソート:【5 4 4 4 3 6 2 1 0】7第2ソート:【4 3 3 5 2 1 0】6 7第3ソート:【3 4 4 4 2 1 0】5 6 7第4ソート:【3 2 1 0】4 5 6 7 5回目のソート:【2 1 0】3 4 5 6 7 6回目のソート:【1 0】2 3 4 5 6 7 7 7回目のソート:【0】1 2 3 4 5 6 7終了
選択ソート時間複雑度O(n^2)余分空間複雑度O(1)(0-n-1最小を0位置に、1-n-1最小を1位置に、・・・、ソート完了まで)7 5 4 3 6 2 1 0第1回ソート:0【7 5 4 3 6 2 1】第2回ソート:0 1【7 5 4 3 6 2】第3回ソート:0 1【7 5 5 4 4 3 6 6】第4回ソート:0 15回目ソート:0 1 2 3 4【7 5 6】6回目ソート:0 1 2 3 4 5【7 6】7回目ソート:0 1 2 3 4 5 6【7】終了
挿入ソート時間複雑度O(n^2)余分な空間複雑度O(1)複雑度は配列中の数字の配列と関係があり秩序が最も良いO(n)無秩序最悪O(n^2)(0-0ソート;0-1ソート;0-2ソート2と1を比較し、交換すると1を0と比較する;0-3ソートを後から前へ比較し、適切な位置に挿入する......、ソートが完了するまで)7 5 4 3 6 2 1 0最初のソート:7【5 4 3 6 1 0】2回目のソート:5 7【4 3 6 2 1 0】3回目のソート:4 5 7【3 6 2 1 0】4回目のソート:3 4 5 7【6 2 1 0】5回目のソート:3 4 5 6 7【2 1 0】6回目のソート:2 3 4 5 6 6 6 6 6【1 0】7回目のソート:1 2 3 3 4 4 5 6 6【0】8回目のソート:0
対数器:利点:1>case検証2>ビッグデータのcaseエラーの原因を特定する3>欲張り戦略ステップ:1、現在、その正確性をテストしたい方法a 2があり、既存の絶対的に正確だが複雑度があまりよくない方法b(同様に方法aの機能を実現する)3、ランダムサンプル生成器を実現してランダムな数Mathを生成する.random()4、a,bメソッドの比較(isEqual)5を実現し、a,bを何度も比較してメソッドaが正しいかどうかを検証し、1つのサンプルで比較エラーが発生した場合、印刷サンプル分析はどのメソッドエラー7であり、サンプル数が多い場合、比較テストは依然として正しいので、メソッドaが正しいと判断することができる.
******テスト配列、ツリー、ヒープ、文字列ランダムジェネレータ
再帰アーカイブ(すべての情報をシステムスタックに押し込む:数行+すべての変数、パラメータの値に実行する)、サブプロシージャを呼び出す
集計ソート時間複雑度O()余分空間複雑度O(n)(配列を2つの部分に分け、両側を並べ替え、並べ替えた後に2つのポインタを設定し、1つの補助配列を増やして並べ替えたデータを格納し、ポインタに対応する2つの値を比較し、小さな格納補助配列を後ろに移動し、そのうちの1つの数のグループが空または空になるまで移動します.そのうちの1つが空であれば、2つを直接すべて補助データに格納し、戻り可)T(N)=aT(n/2)+O(N)時間複雑度O(N*logn)
集計ソートの適用小和問題1つの配列では,各数の左側に現在の数より小さい数が加算され,この配列の小和と呼ばれる.1つの配列の小和を求めます.方法1:各位置の左側に時間複雑度O(N^2)を遍歴する方法2:集計ソートか配列を先に2つの部分に分け、左側が右側より小さいものをresに加算するか.次に細分化された左側が右側より小さいものをres,......,配列がすべてソートされるまで加算する.

public class Test{
	public static int mergerSort(int[] a,int left,int right){
		//          ，           ；
		if(left == right)
			return 0;
		int mid = left + (right-left)/2; 
		return mergeSort(a,left,mid)+mergeSort(a,mid+1.right)+merge(a,left,mid,right);
	}
	public static int merge(int[] a,int left,int mid,int right){
		int i,j;
		int index = 0;   //        
		int[] temp = new int[right-left+1];//    
		int res = 0;		//  
		while(i <= mid && j <= right){
			res += a[i]a[j]?a[j]:a[i];
}
while(i <= mid){
temp[index++] = a[i++];
}
while(j <= right){
temp[index++] = a[j++];
}
return res;
}
}

オーバーフローしやすい:mid=(left+right)/2オーバーフローしない2つの書き方:mid=left+(right-left)/2 mid=left+(right-left)>>1
逆順序ペアの問題1つの配列で、左の数が右の数より大きい場合、この2つの数は逆順序ペアを構成し、すべての逆順序ペアを印刷します.上の考えと似ています.配列を先に2つの部分に分割し、各部分を比較して逆シーケンスペアを印刷します.次に左右の2つの部分の大きさを判断し、逆シーケンスペアを印刷します.同じ数値を指すまで逆順対数が0であることを返します.

public class Test{
	public static void reverseSequence(int[] a,int left,int right){
		if(left == right)
			return;
		int mid = left + (right-left)>>1;
		reverseSequence(a,left,mid);
		reverseSequence(a,mid+1,right);
		printSequence(a,left,mid,right);
	}

	public static void printSequence(int[] a,int left,int mid,int right){
		int i,j;
		int index = 0;
		int[] temp = new int[right - left +1];
		while(i <= mid && j <= right){
			if(a[i] < a[j]){
				int t = j;
				while(t < right){
					System.out.println("   ："+a[i]+","+a[t]);
				}
				temp[index++] = a[i++];
			}
			else
				temp[index++] = a[j++];
		}

		while(i <= mid)
			temp[index++] = a[i++];
		while(j <= right)
			temp[index++] = a[j++];
			
		for(int k = 0;k < temp.length;k++){
			a[left+k] = temp[k];
		}
	}
}