---
# System prepended metadata

title: 分治法 (divide & conquer)
tags: [基礎算法]

---

---
title: 分治法 (divide & conquer)
tags: 基礎算法
---
# 分治法 (divide & conquer)

:::info
- 預備知識：基礎遞迴、排序是什麼
:::

## 分治法核心思想：
- 大問題  ->  分割（通常對半切） ->  小問題（不重複的小問題）-> 合併(把小問題的解快速合併) -> 解答

## 合併排序法（merge sort）
:::info
題目：
- 給n個數字，$A_1, A_2, ... A_n$，由小到大輸出

Constraints:
- $1 <= n <= 200000$
:::
:::success
定義子序列
- $L = {A_1, A_2, ... A_{n/2}}$ sorted
    $L$->$L$ = ${A_1, A_2, ... A_{n/4}}$
    $L$-$R$ = ${A_{n/4+1}, ... A_{n/2}}$
    ...
    $L$->...->$L$ = ${A_1}$ one element is sorted
- $R$ = ${A_{n/2+1}, ... A_n}$ sorted

遞迴完後，
接下來要MERGE！！！

Merge($L$, $R$) => $A$ (must be sorted) 
- e.g.
$L = {1,3,4,8} |L|$
$R = {2,4,6,9} |R|$
=> $A$ will be $\{1,2,3,4,4,6,8,9\}$

Time complexity for merge only: $O(|L| + |R|)$

估計總體時間複雜度：
- $n$
- 第1層 => $\{n/2, n/2\}$
- 第2層 => $\{n/4, n/4\}, \{n/4, n/4\}$
- ...
- 第$logn$層=> $\{1, 1\}, ... \{1, 1\}$

MERGE!!
- 第$logn$層=> $\{1, 1\}, ... \{1, 1\}$ (sorted each other)
- 第$logn-1$層 => $\{2, 2\}, ... \{2, 2\}$ (sorted each other)
- ...
- 第2層 => $\{n/4, n/4\}, \{n/4, n/4\}$ (sorted each other)
- 第1層 => $\{n/2, n/2\}$ (sorted each other)
 
 Time complexity: $O(nlogn)$
 
:::

## 逆序數對

:::info
題目：
- 給一個序列n個元素，求使用bubble sort排序使其由小到大一共要交換幾次。
- 定義逆序數對：$i < j$ && $A_i > A_j$ (for i={1~n}, j={1~n})

Constraints:
- $1 <= n <= 200000$

:::
:::success

$A_1, A_2, ... A_n$

子序列
$L$ = ${A_1, A_2, ... A_{n/2}}$ sorted
    $L$->$L$ = ${A_1, A_2, ... A_{n/4}}$
    $L$->$R$ = ${A_{n/4+1}, ... A_{n/2}}$
    ...
    $L$->...->$L$ = ${A_1}$ one element is sorted
$R$ = ${A_{n/2+1}, ... A_n}$ sorted
MERGE!!!

1. 算出逆敘述對：$i < j$ && $A_i > A_j$ (for i=idx(L), j=idx\(R\))
2. Merge Sort!!
- e.g.
    $L$ = $\{1,3,4,8\} |L|$
    $R$ = $\{2,4,6,9\} |R|$
    => $A$ will be $\{1,2,3,4,4,6,8,9\}$
    $count_A = count_L + count_R + 5$
    $5$ stand for $(3,2), (4,2), (8,2), (8,4), (8,6)$

Time complexity for merge only: $O(|L| + |R|)$

總體時間複雜度：
Time complexity: $O(nlogn)$

:::

## 作業
***至少寫完基礎題喔～***

\*表難度，\*越多難度越高，最高5顆\*
[PA 基礎題 \*\-\-\-\-](https://tioj.ck.tp.edu.tw/problems/1080)
[PB 進階題 \*\*\*\*\-](https://zerojudge.tw/ShowProblem?problemid=c571)
[PC 經典題 \*\*\*\*\-](http://domen111.github.io/UVa-Easy-Viewer/?10245)