分割征服

5697 ワード
algorithm 分割征服 テキストリンク

分割征服

  • 設計ポリシー
  • 分割:解決すべき問題を複数の小部分に分ける.
  • 征服:分かち合う小さな問題をそれぞれ解決する.
  • 統合:(必要に応じて)ソリューションを収集する.
  • Top-down approach

    • 📌繰り返し比較二乗


  • 反復アルゴリズム時間複雑度:O(n)
  • C条=Cは1回乗ります.

  • 分割征服アルゴリズム時間複雑度:O(log 2 n)
  • 分割征服反復平方ヤード
    •     long exp(long x, long y){
    	long r = exp(x,y/2);
    	long res = r*r;
    
    	if(y==1) return x;
    	
    	if(y%2==1) res *= x; //홀수일 때
    	
    	return res;
    }
  • nが大きくなると,分割征服は反復アルゴリズムよりもずっと速くなる.

    • 📌バイナリサーチ

  • 資料センター項目のキー値と比較して、次の検索の場所を特定して検索を継続する方法
  • 目的キーが見つかるまでループでバイナリ検索を行い、検索範囲を半分に絞り込みながら検索をより速く行う

  • バイナリ検索を行うには、資料をソートする必要があります.

  • 時間複雑度:O(log 2 n)

  • サーチプロセス
  • 資料中央の要素を選択する.
  • 中央要素の値と探している目標値を比較します.
  • 中央要素の値と探している目標値が一致すれば探索を終了する.
  • ターゲット値が中心要素値より小さい場合は、資料の左半分に対して新たな検索を行い、
    大きければ、資料の右半分を新たに検索します.
  • 検索する値が見つかるまで、上記の手順を繰り返します.
    • static int binarySearch(int[] arr, int key) {
	//arr은 정렬된 오름차순배열이어야 한다.
	int start = 0, end = arr.length-1;

	while(start<=end) {
		int mid = (start+end) / 2; //중간위치

		if(arr[mid] == key) {
			return mid;
		} else if( arr[mid]<key) {
			start = mid +1;
		} else {
			emd = mid-1;
		}

		//못찾았다면
		return -1;
		
	}
}
    CSS—(5)メディアQuery練習
    [noip 2017]普及グループT 2