---
# System prepended metadata

title: Algo-hw3
tags: [Algorithm]

---

# 演算法作業三
## 觀念題
### 第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$舉例
        ![image](https://hackmd.io/_uploads/SyC7kBvpp.png)
    - 用剛剛的觀察我們可以看到$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可能搜尋的結果畫二元樹可以長這樣：
    
    ![image](https://hackmd.io/_uploads/H1QutBvp6.png)
    
    - 深度：$\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次數
    ![image](https://hackmd.io/_uploads/Hyju8Jca6.png)
    - 問題來了，$\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
    ```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;
        }
    }
    ```
    :::
- 執行結果
    ![image](https://hackmd.io/_uploads/S1NEiEra6.png)
- 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
    ```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];
            }
        }
    }
    ```
    :::
- 執行結果
    ![image](https://hackmd.io/_uploads/BkS2oVB6a.png)
- 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
    ```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 
        }
    }
    ```
    :::
- 執行結果
    ![image](https://hackmd.io/_uploads/Sy_H2VH6a.png)
- 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. 這個區間正在遞增
           ![image](https://hackmd.io/_uploads/HJqFC0IT6.png)
           - 因為正在遞增 => 山鋒一定在右邊 => 找右邊
        2. 這個區間正在遞減
            ![image](https://hackmd.io/_uploads/SknOyJPaT.png)
            - 因為正在遞減 => 山鋒一定在左邊 => 找左邊
        3. 均不是
            ![image](https://hackmd.io/_uploads/SklUgyva6.png)
            - 代表山鋒就在這裡，可以直接回傳
            - ~~其實我打思路才突然發現我沒討論這個case，但後來想想，其實我也是對的，因為到後來while迴圈終止的時候left一定就會跑到山頂~~
    
### 第6題：在平移後的數列中，尋找最小值
[leetcode 852](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)
- 程式碼
    :::spoiler rust
    ```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  
        }
    }
    ```
    :::
- 執行結果
    ![image](https://hackmd.io/_uploads/S1Jv2VHaT.png)
- 完成程度：有參考網路
    - [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. 再來，就簡單了我們找到斷崖，那我們可以分兩種狀況討論
        - 斷崖存在中間
            ![image](https://hackmd.io/_uploads/SyhNVJP6a.png)
        - 完全沒有斷崖
            ![image](https://hackmd.io/_uploads/Skxw4kwp6.png)
        我們可以公式化減少行數：簡化成$peak \space mod \space nums.size()$

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

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

