# 複雜度
***統整自AP325***
為了估計程式的執行效率，~~並且為了二分搜的優勢鋪路~~，在這裡做複雜度的介紹。
## 估算方式
複雜度$O(f(n))$，念作Big-O，**一定要大寫**，小寫有不同意思，習慣上以n表示資料量，複雜度所代表的意思為｢**當資料量為n時，這個程式(演算法)的執行時間(執行指令數)不超過$f(n)$的某個常數倍**」 其中資料量可以是字串長度、輸入數量等，常見的複雜度有$O(log(n))、O(n)$、$O(nlog(n))、O(n^2)等$，計算中有以下幾個原則:
:::success
* $O(2n)=O(3n)=O(n)$，因為根據定義，我們不在乎常數倍。
* 兩個函數相加的Big-O等於比較大的函數。也就是說，當n落在足夠大時，當$f(n)>=g(n)$時，$O(f(n)+g(n))=O(f(n))$，總的來說，找最差的那個當作複雜度即可。
* 若某段程式的複雜度$O(f(n))$執行了$g(n)$次，複雜度為$O(f(n)*g(n))$
* 複雜度計算時找最大的n來計算(worst-case)
:::
## 例子

for(int i=0;i<n;i++)
    total+=a[i]*i;

以這個程式來說，需要做 +=,\*,i++,i<n 四個運算，所以複雜度是O(4n)，根據定義，我們會描述為O(n)。

**PS.sort的時間複雜度為O(nlogn)**

## 資料量對應複雜度
以1秒為例，現在電腦大約可以處理$10^8$~$10^9$的資料量，所以可以整理出下表

| n(大約) | 10^18^ | 10^9^ | 10^6^ | 10^4^ | 10 |
| ------- | ----------- | ------ | ---------- | -------- | ------ |
| 複雜度 | $O(log(n))$ | $O(n)$ | $O(nlogn)$ | $O(n^2)$ | $O(n!)$ |

# 線性搜尋
在學習迴圈的時候，我們曾經用for迴圈作為搜尋的方法

for(int i=0;i<n;i++)
{
    if(a[i]==2)
    {
        cout<<"Found 2 in "<<i<<endl;
    }
}

以剛剛的估算法中，時間複雜度為O(n)，優勢為簡單好寫，但缺點是在資料超過$10^9$時會TLE
# 二分搜
## 原理
在尋找一群已經排序好的資料中，每次都將現在的資料分為一半，因為已經排序的關係，只須所以只需看中間那個數字大於或小於欲尋找的數字，選擇適合的區間直至搜尋到為止。
## 時間複雜度
(直接記住結論即可)
已知每次折半的時間複雜度為O(1)，因為是在做數學運算。
因為每次都將資料折半，假設有n筆資料。
:::success
第一次剩下n/2
第二次剩下n/4
.
.
.
第m次剩下n/2^m^
:::
假設在最差的情況下，第m次搜尋到，也就是$n/2^m=1$，解得$2^m=n$等於$lg(n)=m$，所以時間複雜度為

$O(m)=O(lg(n))=O(log(n)/log(2))=O(log(n))$

相較於線性搜尋的$O(n)$，二分搜的$O(log(n))$相對較佳，但對於無序的情況下，排序的時間複雜度為$O(nlog(n))$，所以在正常情況下還是會選用線性搜尋。

## 實作
### 維護左右端點
這是相對較為傳統的一種二分搜方法，選擇將維護的區間(常用左閉右開，也就是\[a,b))作為迴圈變數來運算。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int wannafind=836,right=1000,left=1;
    while(left<=right)
    {
        int mid=(left+right)/2;
        cout<<left<<' '<<right<<endl;
        if(wannafind==mid)
        {
            cout<<wannafind<<" Find "<<mid<<endl;
            break;
        }
        if(wannafind>mid)
            left=mid+1;
        if(wannafind<mid)
            right=mid-1;
    }
}

### 用跳的!
將一開始放在0，第一次跳總距離的一半，接下來每次跳的距離都砍半，能跳就往前跳，直到找到為止。這樣寫的好處是相較於傳統的更不容易寫錯，因為不須注意範圍。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int wannafind=835,n=0,sizes=1000;
    for(int jump=sizes/2;jump>0;jump>>=1)//jump>>=1等價於jump/=2
    {
        if(n+jump==wannafind)
        {
            cout<<"Find"<<endl;
            break;
        }
        while(n+jump<wannafind)
        {
            n+=jump;
            cout<<n<<endl;
        }
    }
}

### lower/upper bound
這裡套用C++既有的函式庫，作為簡單方便的搜尋用，但相對制式，所以還是要會實作。
* lower_bound:尋找最小且**不小於**所需的數
* upper_bound:尋找最小且**大於**所需的數

通式
:::success
lower_bound(起始指標,終止指標,欲尋找之數);
upper_bound(起始指標,終止指標,欲尋找之數);
:::
兩者皆回傳欲尋找之數的指標。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[10]={1,15,23,45,67,89,234,453,675,897};
    cout<<*lower_bound(a,a+10,234)<<endl;
    cout<<*upper_bound(a,a+10,234)<<endl;
}