# 演算法 HW2

## :book: 觀念題
<mark>**Big-O : 時間函式上的上限(Upper bound)。**</mark>

:::info
**f(n)=O(g(n))
iff 存在正常數C,n0，使得\|f(n)\|<=\|c*g(n)\|，n>=n0。**
:::
### 第一題 
* 時間複雜度(係數設為1，保留最高項): O(n^3^)
* 求最小c及n0
f(n)=O(n^3^)=O(g(n)) --> g(n)=n^3^
令c=最大項係數值+1 --> **c=3+1=4**
f(n)<=cg(n) --> 3n^3^-5n+6 <= 4n^3^
--> **n=1**

| n | \|f(n)\|=\|3n^3^-5n+6\| | \|cg(n)\|=\|4n^3^\| |
| --- |:--------------:|:----------:|
| 1 | 4 | 4 |
| 2 | 20 | 32 |

### 第二題 
* 時間複雜度(係數設為1，保留最高項): O(n^2^)
* 求最小c及n0
f(n)=O(n^2^)=O(g(n)) --> g(n)=n^2^
令c=最大項係數值+1 --> **c=2+1=3**
--> **n=21**

| n | \|f(n)\|=\|2n^2^-100n-50\| | \|cg(n)\|=\|3n^2^\| |
| --- |:------------------:|:-----------:|
| 1 | 148 | 3 |
| 2 | 242 | 12 |
| 10 | 850 | 300 |
| 20 | 1250 | 1200 |
| 21 | 1268 | 1323 |

## :desktop_computer: 程式題 (使用語言 : C++)

### 第三題 二元搜尋應用：當數字可以重覆

* leetcode 33
* 時間:2小時
* 自己完成的程度 : 完全靠自己
* 思路 :
:::success
自己舉了幾個例子，歸納出
:::
* 程式碼 :

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        int mid;
        int ans=-1;
        
        while(left<=right)
        {
            mid=left+(right-left)/2;
            
            if(nums[mid]==target)
            {
                ans=mid;
                break;
            }
            if(nums[mid]>=nums[left])                          // mid之前為排序好的
            {
                if(nums[mid] > target && nums[left]<=target)  // target在left與mid之間
                {
                    right=mid-1;
                }
                else                                          // target在mid之後
                    left=mid+1;
            }
            else if(nums[mid]<nums[left])                     // mid之後為排序好的
            {
                if(target>nums[mid] && nums[right]>=target)  // target在mid與right之間
                    left=mid+1;
                else                                          // target在mid之前
                    right=mid-1;
            }
            /*
            else
            {
                if(nums[mid]>target && target>=nums[left])
                    right=mid-1;
                else
                    left=mid+1;
            }
            */
        }
        return ans;
    }
};

* 通過截圖


### 第四題 數字可能重複，回傳範圍

* leetcode 34
* 時間:1小時
* 自己完成的程度：完全靠自己
* 思路 :
:::success
因為數列已經排序好了，所以當我們使用二元搜尋法找到題目所需要的target後，開始往前/後找，直到找到不是target的那個數字為止。
:::
* 程式碼:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0)
        {
            vector<int> ans;
            ans.push_back(-1);
            ans.push_back(-1);
            return ans;
        }
        int left=0;
        int right=nums.size()-1;
        int mid;
        int index1=-1;
        int index2=-1;
        while(left<=right)
        {
            mid=left+(right-left)/2;
            if(nums[mid]<target)
                left=mid+1;
            else if(nums[mid]>target)
                right=mid-1;
            else
            {
                index1=mid;
                if(index1+1<nums.size())
                {
                    while(nums[index1+1]==target)
                    {
                        index1++;
                        if(index1+1>=nums.size())
                            break;
                    }
                }
                
                index2=mid;
                if(index2-1>=0)
                {
                    while(nums[index2-1]==target)
                    {
                        index2--;
                        if(index2-1<0)
                            break;
                    }
                }
                break;
            }
        }
        vector<int> ans;
        ans.push_back(index2);
        ans.push_back(index1);
        return ans;
    }
};

* 通過截圖


### 第五題 猜數字遊戲

* leetcode 374
* 時間:10分鐘
* 自己完成的程度：完全靠自己
* 思路 :
:::success
和leetcode278類似，使用二元搜尋法找數字。
當guess()回傳-1，表示猜的數字太大，因此往左邊找(right=mid-1)。
當guess()回傳1，表示猜的數字太小，因此往右邊找(left=mid+1)。
當guess()回傳0，表示猜到數字了，因此結束迴圈並回傳該數字。
:::
* 程式碼:

class Solution {
public:
    int guessNumber(int n) {
        int left=1;
        int right=n;
        int mid;
        int ans=1;
        while(left<=right)
        {
            mid=left+(right-left)/2;
            
            if(guess(mid)==-1)    //num > pick
                right=mid-1;
            else if(guess(mid)==1)//num < pick
                left=mid+1;
            else if(guess(mid)==0)  //num = pick
            {
                ans=mid;
                break;
            }
        }
        return ans;
    }
};

* 通過截圖


## :pushpin:心得

### 第六題 本週心得

這次作業跟上次比起來，個人覺得難度跳蠻多的，有一題甚至舉了幾個例子才統整出一個方法，雖然程式作業少了一題，但還是花了很多時間，甚至快比上一週花的時間還更多。

###### tags: `演算法`