分割征服

5834 ワード
アルゴリズム#アルゴリズム# テキストリンク
すべての写真資料の出所は以下のAltubTutoringにあります.
https://github.com/Altu-Bitu/Notice

🕎分割征服


  • 一度では解決できない問題を小さな問題に分割して解決するアルゴリズムex)集計ソート
  • 大問題→小問題→上から下へ!
  • 主に再帰関数に現れる
  • 分割方法による時間複雑度千差万別
  • 入力範囲Nが大きい
  • 大きく分けて3段階
  • Divide:分割問題
  • Conquer:小問題解決
  • Combine:解決した小さな問題を再統合

    • 分割征服を用いて問題を解決すれば
    ▶O(logN)消費電力計算の問題を解決!
    long long power(int n, int k) {

	if (k == 1) //Conquer
		return n;

	//Divide + Combine
	if (k % 2 == 0) //지수가 짝수
		return power(n * n, k / 2);

	else //지수가 홀수
		return n * power(n * n, (k-1) / 2);
}

    💎クイックソート

  • ピボットを基準にアレイを半分に分けて並べ替え
  • 時間複雑度は通常O(nlogn)
  • ロボットの選び方によると、最悪の場合はO(N 2)の時間的複雑さかもしれません.
  • 並べ替え手順
  • アレイから1つの要素(pivot)を選択
  • アレイの左側がpivotより小さいエレメント、右側がpivotより大きいエレメント配置
  • 左右の配列に対して1~2の過程を繰り返す
  • アレイサイズが0または1の場合終了

    • 📝クイックソートプロセス

  • pivotの次の位置Left範囲の最後の位置Right
  • まだ完全に分離されていないグループの一番左の要素をピボットに設定します.
  • Leftはpivotより大きい値を指すまで右に移動する.
  • ライトは、ピボット以下の値を指すまで左に移動する.
  • 両方のポインタが停止した場合、swap
  • Left
  • LeftとRight街교차swap Rightが指す要素とpivotが指す要素
    Q.LeftとRightが交差する意味
    A.Leftは左端から、pivotより大きい場合は停止し、Rightは右端から、pivotより小さい場合は停止する.したがって,左<>右の交差が発生し,左左側はpivotより小さい値であり,右側はpivotより大きい値であることを意味する.したがって、この状態でpivot<->権限を交換すると、pivotの左側にはpivotより小さい値が配置され、pivotの右側にはpivotより大きい値が配置されます.

    • 📗代表的な問題


    BOJ）2630：色紙を作成する




    BOJ)4256:後列巡り





    結論
    プリソート(前列順)
  • 部分木の根は当該部分木の一番左側にある
  • ルート以降、左側サブツリーのノードは右側サブツリーのノードに接続されている.
    ▶根元の位置はわかりますが、左右の子木の境界はわかりません.
    • Inorder(中尉ツアー)
  • ローカルツリーの根を基準にして左側が左サブツリー、右側が右サブツリーとなります.
    ▶ルートの位置を知るだけで、左、右のサブツリーのノードはわかりますが、ルートの位置はわかりません.
    • preorderでルートノードを決定し、Inorderで左、右のサブツリーを分割します.

    👾の最後の部分

  • 問題に重複演算がある場合、または(ex.星図)Nが大きい場合は分割征服を考慮!
  • 簡単な計算問題ならNは長い範囲に入ることができます.
    • まず考えてみると
  • ・Divide・Conquer・Combine演算は何ですか.
  • 実施方法によって時間の複雑さが異なる.不適切な実施を行うと,分割征服でもタイムアウトが発生する可能性がある.
  • 再帰関数を実現する場合は、基本条件が無限ループに陥らないようにする.

    • これも聞いてみよう。

  • 入力が既にソートされているか、またはソートされている場合は、高速ソートの効率が低下していることを目撃します!では、この場合、迅速なソートの効率を確保するにはどうすればいいのでしょうか.
    • pythonで菱形を印刷する
    Git命令メモ