---
title: Divide and Conquer / Counting Inversion, Closet Pair of Point
tags: 演算法(交大OCW)
---
# Counting Inversion

計算兩個 Sequence 的「相似度」

## 音樂的排名

「Me」跟「You」對於五首歌曲有不同的排名，你想要計算兩個人的排名「不同的部分」；其中會將「Me」的排名以升序的方式列出，也就是下圖的 1,2,3,4,5，並且將「You」的排名對應你的歌曲列出

利用「Inversion」計算「不同的部分」；所謂的「Inversion」，就是將排名如下圖連線後所產生的交叉


:::info
上圖中，將 Me 的排名所對上的歌曲，作為排序的基準，也就是說， Me 的第 1 名就是第 1 首曲子；不過在 Me 心目中第 1 名的曲子，在 You 心目中只有第 2 名

而畫出 Inversion 就是讓「Me」的第 1 名連到「You」的第 1 名，以此類推
:::

### 暴力解

找 Inversion 可以用暴力解，每個都給他查一遍 O(n^2^)

# Divide and Conquer

但是定神一看，會注意到由於 Me 的排名已經排好序了，這時候只要從 You 的排名從左向右一個一個看；只要後面有排名比當前的排名小的，就一定會發生交叉；有幾個比較小就發生幾次交叉

也就是說，如上圖中 You 的第 4 名，後面會遇到 You 的第 1 名跟第 3 名，因此第 4 名會發生兩次交叉

>原本應該在前面的，但是卻跑到了後面，所以必定會有交叉

不過如果音樂太多的話，如下面有 12 首曲子，就需要程式來幫我們執行找「Inversion」的這個過程


- Divide：將曲子列表分成兩半
- 就是簡單的拆成兩半
- Conquer：遞迴地找出「Inversion」
- 拆完兩半後遞迴呼叫 Divide
- 直到拆解後的大小是 1 ，也就是拆到剩 1 個人時就不再繼續拆
- Combine：將「Conquer」完的兩個部分合併在一起
- 合併的時候，就是比較跨兩組間有沒有發生 Inversion
- 舉例來說，由於拆到剩 1 個時就不再拆了，所以會 Combine 只有 1 首曲子的「兩半」

## Combine 的詳細步驟

### Naïve

直觀的想法就是
- 粉紅色那組在左邊，所以要以粉紅色為主
- 從左到右開始一個一個檢查，去對綠色的，一樣從左到右
- 例如粉紅色的第 1 個開始，也就是 1 ；然後綠色從左到右都沒有比 1 小
- 但是都比 1 大，所以沒有發生 Inversion
- 到粉紅色下一個，也就是 5；然後綠色從左到右都沒有比 5 小
- 其中的 3 比 5 小，所以有 Inversion

但是這樣找的話時間就是 O(n^2^)，這樣不太妙

### Clever Method


假如 Combine 後的結果，也就是上圖中粉紅色跟綠色的「兩半」，是排序好的
我以綠色為主，利用一個 index 紀錄粉紅色的「位置」，初始為 0

- 從綠色的第 1 個，也就是 3 開始比。粉紅色的前 2 個都比 3 小
- 直到粉紅色第 3 個，也就是 4 ；此時將 index 移動到 4 所在的位置，代表說目前比到了 4 就發生了 Inversion；並且下次從 4 開始比
- 到綠色的第 2 個，也就是 6 開始比。從粉紅色第 3 個，也就是 4 開始比
- 直到粉紅色第 5 個，也就是 8；此時將 index 移動到 8 所在的位置，代表說目前比到了 8 就發生了 Inversion；並且下次從 8 開始比

因為兩者都是排好序的陣列，由小排到大；在綠色中，不能和第 x 個有 Inversion 的數字，一定也不能和第 x+1 個有 Inversion

這樣子找完「組間 Inversion」就只要 O(n) 的時間

### 額外好處

而且找完「組間 Inversion」後，就可以順便用 Merge Sort 的 Combine 部分做排序的動作，提供上一層所需的「已排序陣列」

### Pseudo Code

跟 Merge Sort 很像，就只有差在需要紀錄並回傳有多少 Inversion 的部分


## 複雜度 O(nlogn)

證明跟 Merge Sort 一模一樣，畢竟內容本身換湯不換藥

---

# Closet Pair of Point

:::info
M. I. Shamos and D. Hoey 1975
:::

在平面灑很多點，找最近的兩個點在哪裡；給你很多點的 xy 座標，去找出最近的兩點

:::success
這裡對於最近的定義是採用歐式距離 Euclidean distance 也就是兩點的直線距離
因為有另一種距離的計算方式是，x 跟 y 座標的差異取絕對值後相加，常用於 IC 繞線
當然還有更多種距離計算方式
:::

## Brute Force

暴力拆解，直接 O(n^2^) 給他弄下去
:::warning
雖然我不是數學家，但這聽起來很不妙對吧
:::

## Clever Method

### 1-D

先來想想 1D，也就是一條線的情況


- 首先要先將他們由小到大排好序；排好序後，假如照順序有 ABC 三點，那麼 AB 的距離一定會小於 AC 的距離
- 因此，我只要檢查連續兩點的距離，並持續記錄最大值就好；這樣就只要掃過一次序列 O(n)
- 不過要記得排序需要 O(nlogn)

### 2-D

2D 很顯然不能這樣做，所以就要使用DAC
:::info
為了分析比較方便，這裡假設所有點的 x 座標都不一樣
不會待會只要小修改一下，就可以通用
:::


- 前置處裡：先將所有點依據 x 座標由小到大排序
- Divide：將所有點依據 x 座標分成兩半；一半不包含 L 的座標，另一半包含 L 的座標
- 也就是從排好序的點中，選位於中間的點出來，以該點的 x 座標分成兩半
- Conquer：遞迴地找出「Inversion」
- 拆完兩半後繼續遞迴地呼叫 Divide
- 直到拆解後的範圍內小於等於 3 個點，這時候就可以直接算距離
- Combine：將「Conquer」完的兩個部分合併在一起
- 合併的時候，先從兩組得到的距離中比較出最小值 $\delta$
- 將這個最小值作為寬度，搜索 (L-$\delta$,L+$\delta$) 範圍內有沒有兩點有更小的距離

### 搜索 (L-$\delta$,L+$\delta$)

如果 (L-$\delta$,L+$\delta$) 範圍內有太多點的話，那也是不太妙的事情，所以這時候要有 Clever 的作法

:::info
- 先將範圍內的點依照 y 座標排序
- 如果在 (L-$\delta$,L+$\delta$) 範圍內，畫出如下圖的 16 個正方格，每個方格長寬固定是 $\frac{\delta}{2}$
- 可以知道假如有兩點落在這整個大正方形區域內的話，必定會落在不同的兩個小方格
- 如果會的話說明這兩點才是最小距離，與上一輪搜索的結果矛盾
- 假設你正在檢查一個點，那你只要檢查他後面的 15 個點就好
:::
:::warning
為甚麼要檢查 15 個點呢？
老師這邊是用反證法：先假設有兩點之間的距離小於 $\delta$ 且是在 16 格之外；由於 16 格保證兩點間距離必定大於 $\delta$ ，造成矛盾，因此是 15 格以內

不過其實還有更細的做法，可以把邊界縮的更小
但這些目的都是為了讓「搜尋」這件事變成 O(n)，而不是 O(n^2^)
因為檢查每個點的時候，不用往後檢查後面 n-1 個點，而是檢查後面 15 個點就好
:::


### Pseudo Code

兩個排序，一個是依照 x 軸，一個是依照 y 軸
x 軸是用來找中間值用；y 軸是用來找 (L-d,L+d) 範圍內的點用

由於遞迴的函式中，除了遞迴的部分，其他都小於等於 O(n)，因此整體複雜度就是 O(nlogn)

sorting 也是 O(nlogn)，所以整體就是 O(nlogn)