# 演算法作業三
## 觀念題
### 第1題: Insertion Sort
1. 請依據課本推導方式，當5個數字用insertion sort排序，data movement的平均值為多少？
:::info
**pf：當5個數字用insertion sort排序，data movement的平均值為多少**
$\exists X$是全部需要移動的次數
則，$X = \Sigma_{i=2}^5(2+d_i)$ $\forall d_i$是全部需要移動的平均次數(從i到0)

那我們要討論的重點就是$d_i$

- 先稍微簡化問題，以$d_5$舉例
- 用剛剛的觀察我們可以看到$d_i$
$\begin{split} d_n + 2(for\space ouuterloop) &= \frac{1}{n}\Sigma_{i=1}^n i+1
\\ &= \frac{n(n+3)}{2n}
\\ &= \frac{n+3}{2}\end{split}$
所以回歸所求：$X = \Sigma_{i=2}^5(2+d_i)$
$\begin{split} X &= \Sigma_{i=2}^5(2+d_i)
\\&=\Sigma_{i=2}^5 \frac{n+3}{2}
\\&= \Sigma_{i=2}^5 \frac{3}{2} + \frac{1}{2}\Sigma_{i=2}^5 n
\\&=13
\end{split}$
:::
> 13
2. 請使用insertion sort排序 6,4,1,3,5。在四個回合中，每回合的data movement數量為何？總共的data movement數量為何？

| **round** | **x1** | **x2** | **x3** | **x4** | **x5** | **movement** |
|:---------:|:------:|:------:|:------:|:------:|:------:|:------------------------------:|
| 0 | 6 | 4 | 1 | 3 | 5 | X |
| 1 | 4 | 6 | 1 | 3 | 5 | 1(inner loop) + 2(outter loop) |
| 2 | 1 | 4 | 6 | 3 | 5 | 2(inner loop) + 2(outter loop) |
| 3 | 1 | 3 | 4 | 6 | 5 | 2(inner loop) + 2(outter loop) |
| 4 | 1 | 3 | 4 | 5 | 6 | 1(inner loop) + 2(outter loop) |
> total：14

### 第2題: Binary Search
1. 請參考投影片25頁與26頁，算出15個有序數列使用Binary Search，平均的比對次數為何？
:::info
**pf：算出15個有序數列使用Binary Search，平均的比對次數為何**
其實二元搜尋可以視為D&C策略，我們將每一step可能搜尋的結果畫二元樹可以長這樣：


- 深度：$\lfloor log 15\rfloor + 1 = 4$
- 元素：$15$

那我們可以帶入公式：$A(n) = \frac{1}{2n+1}[\Sigma_{i=1}^k i2^{i-1} + k(n+1)]$ , $k =\lfloor log n\rfloor + 1$
並使用簡化方式可發現：$A(n) = \frac{1}{2n+1}[2^k(k-1)+1+k(n+1)]$
因此答案是：$\frac{1}{31}(16*3+1+4*16) =3.6451612903225805$
:::
> 3.6451612903225805

:::spoiler 二分搜Average Case證明
~~超級長預告~~

1. case 數
- 成功：代表在1~n個節點中有一個成功被搜尋到 => n個case
- 失敗：代表今天不在list中 => n+1個case
2. 計算average次數
- 問題來了，$\Sigma_{i=1}^k i2^{i-1}$很難計算，因此需要簡化
- [公式證明：直接證明法](https://hackmd.io/_uploads/Hk5DtF9pa.png)
- [referance](https://math.stackexchange.com/questions/2966250/summation-of-sum-i-1n-i2i)
- 簡化過可得：$A(n) = \frac{1}{2n+1}[2^k(k-1)+1+k(n+1)]$
3. 當$n\rightarrow\infty$，n會趨近於$2^k$
$\begin{split}
A(n) &= \frac{1}{2^k}((k-1)2^k+k2^k)\\
&= \frac{k-1}{2} + \frac{k}{2} \\
&= k - \frac{1}{2} \\
&= O(logn)
\end{split}$
:::
## 程式題
### 第3題：完全平方數
[leetcode 367](https://leetcode.com/problems/valid-perfect-square/)
- 程式碼
:::spoiler rust

    impl Solution {
        pub fn is_perfect_square(num: i32) -> bool {
            if (num == 1 || num == 0){
                return true;
            }

            let num = num as usize;
            let mut left  = 1 as usize;
            let mut right = num as usize;

            while left <= right {
                let mid = (right - left) / 2 as usize + left;

                if (mid * mid == num){
                    return true;
                }
                else if (mid * mid > num){
                    right = mid - 1;
                }
                else {
                    left = mid + 1;
                }
            }
            return false;
        }
    }

:::
- 執行結果
- Program Language：Rust
- 完成程度：完全靠自己
- 解題時間：5分鐘
- 思路：
~~這題跟第一周第六題好像~~
1. 把它當成一個數列開始搜尋
:::success
###### 以case1舉例
ans = [$1^2$,$2^2$,$3^2$,$4^2$,$5^2$,$6^2$,$7^2$,$8^2$,$9^2$,$10^2$,$11^2$,$12^2$,$13^2$,$14^2$,$15^2$,$16^2$]
:::
2. 有上面這個東西我們就可以用二分搜搜尋，只要找到直接回傳true，沒有則false

### 第4題：尋找字元
[leetcode 744](https://leetcode.com/problems/find-smallest-letter-greater-than-target/)
- 程式碼
:::spoiler rust

    impl Solution {
        pub fn next_greatest_letter(letters: Vec<char>, target: char) -> char {
            let mut left: i32  = 0;
            let mut right:i32 = letters.len() as i32  - 1;


            while left <= right {
                let mid  = left + (right - left) / 2 ;

                if letters[mid as usize]  <= target  {
                    left = mid + 1;
                }
                else{
                    right = mid - 1;
                }
            }
            if left < letters.len() as i32{
                return letters[left as usize];
            }
            else{
                return letters[0];
            }
        }
    }

:::
- 執行結果
- Program Language：Rust
- 完成程度：完全靠自己
- 解題時間：15分鐘
- 思路：
**核心概念：** 這題其實就是找upperBound
1. 序列都是字母，但是是照ASCII排列 => 符合二分搜的目標!
2. 好所以我們可以使用上禮拜的技巧，二分搜的結果left就是所求
3. 但但但，題目還有特別提不存在的情況回傳`letters[0]`
- **分析:** 假如不存在
- 一定是欲搜尋字母在`letters`中是最大
- 因此這裡可以直接斷言`left >= letters.size()`就直接回傳0
### 第5題：尋找山頂
[leetcode 852](https://leetcode.com/problems/peak-index-in-a-mountain-array/)
- 程式碼
:::spoiler rust

    impl Solution {
        pub fn peak_index_in_mountain_array(arr: Vec<i32>) -> i32 {
            let mut left:i32  = 1;
            let mut right:i32 = arr.len() as i32  - 2;

            while left <= right{
                let mid = left + (right - left) / 2;

                if arr[(mid-1) as usize] <= arr[mid as usize] && arr[mid as usize]<=arr[(mid+1) as usize]{ 
                    //  This Domain is Increasing => search right 
                    left = mid + 1;
                }
                else{
                    // This Domain is Decreasing => search left 
                    // Maybe There is a ans in this domian
                    right = mid - 1;
                }
            }
            left 
        }
    }

:::
- 執行結果
- Program Language：Rust
- 完成程度：有參考網路
- [referance](https://leetcode.com/problems/peak-index-in-a-mountain-array/solutions/3816190/binary-search-100/)
- 解題時間：1小時
- 思路：
~~我這題想超級久~~
1. 從題目可以知道$0 < i < arr.length - 1$，也就是說山鋒絕對不會出現在0與$arr.length - 1$
- 代表搜尋時不討論這裡!!!!
2. 那我們可以分三種狀態討論
1. 這個區間正在遞增
- 因為正在遞增 => 山鋒一定在右邊 => 找右邊
2. 這個區間正在遞減
- 因為正在遞減 => 山鋒一定在左邊 => 找左邊
3. 均不是
- 代表山鋒就在這裡，可以直接回傳
- ~~其實我打思路才突然發現我沒討論這個case，但後來想想，其實我也是對的，因為到後來while迴圈終止的時候left一定就會跑到山頂~~

### 第6題：在平移後的數列中，尋找最小值
[leetcode 852](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)
- 程式碼
:::spoiler rust

    impl Solution {
        pub fn find_min(nums: Vec<i32>) -> i32 {
            let size = nums.len();
            let peak = Self::peak(&nums);
            nums[peak as usize % size]
        }
        fn peak(nums :&Vec<i32>) -> i32{
            let mut left:i32  = 0;
            let mut right:i32 = nums.len() as i32 - 1;

            while left <= right{
                let mid = left + (right - left) / 2;

                if nums[0] <= nums[mid as usize] {
                    // Increase
                    left  = mid + 1;
                }
                else{
                    right = mid - 1;
                }
            }
            left  
        }
    }

:::
- 執行結果
- 完成程度：有參考網路
- [referance](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/solutions/3561649/rust-reusing-solution-to-162-find-peak-element/)
~~其實看完才發現我幹嘛看，上禮拜有寫過類似的斷崖搜尋題~~
- 解題時間：30 分鐘
- 思路：
1. 首先，我們要先找斷崖
- 我們從題意可以知道，上升一定是[0,n]區間當中，因此當`nums[mid]`比`num[0]`大，就代表還沒到斷崖，因此繼續找右邊
- 同裡，如果反過來就左邊
2. 再來，就簡單了我們找到斷崖，那我們可以分兩種狀況討論
- 斷崖存在中間
- 完全沒有斷崖
我們可以公式化減少行數：簡化成$peak \space mod \space nums.size()$

## 心得
這周學了best case, worst case, average case的討論，average case算起來好麻煩，要將全部的情況都考慮一次，我光是觀念題就打了1小時(推理的過程)，但也補足了之前資料結構教sort的概念，我那時對這三種情況的推算感到十分疑惑，今天終於解開了。

好再來說程式題的部分，突然一時興起用rust除外(下禮拜看時間夠不夠再決定要不要繼續用)，然後我寫最久的是山峰那題，我想超級久，結果看到網路上有人的解法馬上覺得我好笨，這世界的電神好可怕，但後來寫完好開心。