アルゴリズム#アルゴリズム#

19324 ワード
algorithm テキストリンク
1)グリディ★★★
  • アルゴリズム(貪欲法)
  • マルチアウトレットアルゴリズム:特定のノードから特定のノードへの最短経路を求めるアルゴリズム
  • クルーズアルゴリズム
    • 2)完全探索★★★
  • すべての場合、数量を計算する必要があるソリューション
  • 組み合わせ、シーケンス
    • を求める
  • は、通常、DFS/BFSアルゴリズム
    • を使用する
    深度優先ナビゲーション幅優先ナビゲーション遠方のノードからナビゲーション近辺のノードからナビゲーション動作原理Stack動作原理Queue実施方法再帰関数実現方法Queueデータ構造
    ※DFSはO(N)の時間が必要です.
    ※通常のDFSよりBFSの実施速度が速い
    3)シミュレーション★★★
  • 問題においてアルゴリズムを段階的に実行する必要がある問題タイプ
    • 4)ダイナミックプログラミング★★★
  • メモリ容量をさらに多くすると、演算速度
    • を大幅に向上させることができます.
  • 条件
    1)大きな問題を小さな問題に分けることができる.
    2)小問題で求めた答えは,それを含む大問題においても同様である.
  • ex)フィボナッチ数列
    • 注記リビルド(キャッシュ)
  • は、一度に得る結果をメモリ領域に記録し、同様の方法を呼び出し、結果はそのまま
    • となる.
    タワー
  • 大きな問題を解決するために小さな問題を呼び出す
    • データムアップ(繰り返し)
  • 小さい頃から質問に逐次漸進的に答え始めた
  • DPテーブル:結果を保存するためのリスト
    • 5)並べ替え
    ソートの選択
  • 最小の繰返しを最上位のアルゴリズム
    • に送信することを選択する.
  • 時間複雑度:O(N)²)
    1)すべてのデータで最小値を選択し、一番前に移動します.
    2)最小値を選択し、並べ替えられていないデータの一番前に繰り返し移動します.
    • //선택정렬 예제
for(int i=0; i<10; i++) {
	int min_index = i;
	for(int j=i+1; j<10; j++) {
		if(arr[min_index] > arr[j]) {
			min_index = j;
		}
	}
			
	int temp = arr[i];
	arr[i] = arr[min_index];
	arr[min_index] = temp;
}
    整列挿入
  • 特定のデータを適切な位置に挿入するアルゴリズム
  • データが位置合わせに近い場合、遊離
  • 時間複雑度:O(N)²) ~ O(N)(整列時にO(N))
    1)最初の値がソートされたとします.
    2)次のデータがソートされたデータのどの位置に入るかを判断し,繰り返し挿入する.
    • for(int i=1; i<10; i++) {
	for(int j=i; j>0; j--) {
		if(arr[j] < arr[j-1]) {
			int temp = arr[j];
			arr[j] = arr[j-1];
			arr[j-1] = temp;
		} else {
			break;
		}
	}
}
    クイックソート
  • 標準を設定し、大数と小数の交換を繰り返すアルゴリズム
  • 軸心:交換規格
  • データは、位置合わせに近づくと遅くなる(挿入位置合わせとは逆)
    • .
  • 時間複雑度:O(Nlogn)~O(N)²)
    1)リスト内の最初のデータがピボット
    2)ピボットより大きいデータを左から右、ピボットより小さいデータを右から選択
    3)両データの位置変更
    4)2つの値が交差する場合は、小さなデータとピボットの位置を変更します.
    5)再帰呼び出しにより左右を分割し,それぞれソートする.
    • public static void quickSort(int[] arr, int start, int end) {
	//리스트에 원소가 1개면 종료
	if(start >= end) {
		return;
	}
		
	int pivot = start;
	int left = start+1;
	int right = end;
		
	while(left <= right) {
		//피벗보다 큰 데이터를 찾을 때까지
		while(left <= end && arr[left] <= arr[pivot]) {
			left++;
		}
			
		//피벗보다 작은 데이터를 찾을 때까지
		while(right > start && arr[right] >= arr[pivot]) {
			right--;
		}

		if(left > right) {
			//엇갈리면 작은 데이터와 피벗 교체
			int temp = arr[pivot];
			arr[pivot] = arr[right];
			arr[right] = temp;
		} else {
			//엇갈리지 않았다면 작은 데이터과 큰 데이터 교체
			int temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
	}
		
	//분할 이후 왼쪽, 오른쪽 각각 정렬
	quickSort(arr, start, right-1);
	quickSort(arr, right+1, end);
}

quickSort(arr, 0, 9); //메인함수 호출부(배열, 시작인덱스, 끝인덱스)
    ソート数
    アルゴリズムは、
  • のデータの範囲が限られている場合にのみ使用することができる.
  • データの最大値配列を作成し、ソート情報
    • を含む
  • 時間複雑度:O(N+K)(Kは最大データ量)
    1)データの最大値に従ってインデックス配列を作成する
    2)データ値と同じインデックスデータを1ずつインクリメント
    3)インデックスサイズで出力
    • public static final int MAX_VALUE = 9;

for(int i=0; i<15; i++) {
	cnt[arr[i]]++;
}

//출력
for(int i=0; i<=MAX_VALUE; i++) {
	for(int j=0; j<cnt[i]; j++) {
		System.out.print(i + " ");
	}
}
    6)バイナリナビゲーション
  • アレイのデータは、
    • を使用するには整列する必要があります.
  • ナビゲーション範囲を半分に縮小します.
    • ナビゲーション
  • 時間複雑度:O(logn)
    1)中点は(始点+終点)/2
    2)検索値が中間点より小さい場合は、左側から
    3)検索値が中間点より大きい場合は、右側
    4)始点が終点より大きい場合は終了
    • public static int binarySearch(int[] arr, int target, int start, int end) {
	if(start > end) {
		return -1;
	}
		
	int mid = (start + end) / 2;
	if(arr[mid] == target) {
		return mid;
	} else if(arr[mid] > target) {
		return binarySearch(arr, target, start, mid-1);
	} else {
		return binarySearch(arr, target, mid+1, end);
	}
}

int result = binarySearch(arr, target, 0, n-1); //메인함수 호출부
    7)最短パスアルゴリズム
    マルチアウトレットアルゴリズム
  • ある点から別の点への最短経路
    • を求める.
  • 階調アルゴリズム
  • 優先キューを使用して
    • を実施する.
  • 時間複雑度:O(V)²) ~ O(V:ノード数,E:幹線数)
    • りゅうすいアルゴリズム
  • すべての場所からすべての他の場所までのすべての最短経路
    • を求める
  • 動的プログラミングアルゴリズム
  • 時間複雑度:O(N)³)
    • [2019ココ冬季実習]Q 05ホテルの部屋を割り当てる(JAVA)
    Android学習のIntentに表示される意図と暗黙的な意図の用法例の分析