複雜度分析 & 質數判定

計算大概的執行次數

執行次數無法完全精準的計算
可能受到編譯器優化影響
使得執行次數不是我們所計算的
而只需要計算大概的次數就可以去估算時間

表達時間複雜度

• 以大\(O\)符號表示，其中大\(O\)符號代表 "上限" 的意思

計算時間複雜度

1. 估計程式的運算執行次數
2. 將得到的函數最高階項以外的項全部刪掉
3. 把係數拿掉

迴圈的時間複雜度

迴圈的執行次數*每次迴圈的時間複雜度

for(int i=0;i<n;i++)
{
    arr[i]=arr[i-1]*a+b;    //O(1)
    swap(a,b);    //O(1)
}

\(O(n)\)

for(int i=0;i<n;i++)
{
    for(int j=i+1;j<n;j++)
    {
        if(arr[i]>arr[j])
            swap(arr[i],arr[j]); //O(1)
    }
}

執行次數大約是\((n-1)+(n-2)+...+1+0=\frac{1}{2}n(n-1)=\frac{1}{2}n^2+\frac{1}{2}n\)

保留最高階項，省略常數

因此時間複雜度是\(O(n^2)\)

for(int i=1;i<n;i*=2)
    s+=i;

\(2^i\lt n\Rightarrow i\lt lgn\)
因此是\(O(\log n)\)

在算複雜度時，通常 \(\log\)、\(log\) 代表以 \(2\) 為底取 \(log\)

遞迴函數的時間複雜度

• 簡單的你們應該會算(?)
• 比較難的等教分治法(Divide&Conquer)時再說
• 很複雜的我也不會

內建函數的時間複雜度

其實從函數的功能應該可以猜出其複雜度
不然的話就把它記起來(至少常用的函數要知道)
例：memset O(N)、 sort O(NlgN)、 __gcd O(lgN)、lower_bound O(lgN) …

實作範例分析

for(int i=100000;i<n;i++)
{
    for(int j=i-100;j>=1000;j--)
        cout<<i<<" "<<j<<'\n';
}

for(int i=10;i<n;i++)
{
    for(int j=i-100;j>=1000;j--)
        cout<<i<<" "<<j<<'\n';
}

\(O(n^2)\)

for(int i=0;i<100000000;i++)
    cin>>n,cout<<n*n<<'\n';

for(int i=0;i<100000000;i++)
    cin>>n,cout<<n*n<<'\n';

\(O(1)\)

for(int i=1;i<=n;i++){
    sort(arr,arr+i);
}

for(int i=1;i<=n;i++){
    sort(arr,arr+i);
}

\(O(n^2lgn)\) \((\sum\limits_{k=1}^{n}klgk\approx n^2lgn)\)

for(int i=1;i<n;i=i*2){
    for(int j=i;j<n;j+=i)
        arr[j]+=arr[j-i];
}

for(int i=1;i<n;i=i*2){
    for(int j=i;j<n;j+=i)
        arr[j]+=arr[j-i];
}

\(O(n)\) \((n+\frac{n}{2}+\frac{n}{3}+...\approx 2n)\)

void f(int n)
{
    if(n==0) return 1;
    return f(n-1)*n;
}

void f(int n)
{
    if(n==0) return 1;
    return f(n-1)*n;
}

\(O(n)\)

void f(int i){
    if(i==n) return;
    v[i]=0,f(i+1);v[i]=1,f(i+1);v[i]=2,f(i+1);
}

void f(int i){
    if(i==n) return;
    v[i]=0,f(i+1);v[i]=1,f(i+1);v[i]=2,f(i+1);
}

\(O(3^n)\)

為什麼要學時間複雜度

• 判斷一個程式(做法)會不會TLE
• 可以用側資的範圍去反推演算法

1. 把時間複雜度的大\(O\)符號拿掉，並將題目給定的輸入範圍上限帶入函數，令得到的數值為 \(T\)

2. 一般而言假設c++每秒能跑 \(10^8\) 的數量級

3. 假設題目的時限是TL秒，那麼

   • 若\(T\lt TL\times 10^8\)則通常不會TLE
   • 若\(T\gt TL\times 5\times 10^8\)則極有可能拿到TLE

時間複雜度的好處

• 當你想到一個做法後，在開始寫之前就能先用時間複雜度來判斷是否會 TLE，以避免浪費時間在寫必然會 TLE 的程式

• 在比賽中更容易作時間分配、難度分析

對於範圍內的數字使用快速的方法判斷它是否為質數。

方法一 窮舉

詢問數字 \(N\) 是否為質數?

窮舉每個小於 \(N\) 的數字，判斷該數字是否整除 \(N\)
若整除代表枚舉的該數字是 \(N\) 的因數

以 \(7\) 為例子，我們要跑一個迴圈從 \(2\) 跑到 \(6\) 並且用每一個數字去除除看。

最差情況 : 判斷的數字是質數，因此要跑 \(2\sim N-1\) 總共 \(N-2\) 個數字 (除了 \(1\) 跟 \(N\) )

簡單的快速判斷，暴力跑過每個數字

int n;
cin>>n;
for(int i=2;i<n;i++){
    if(n%i==0){  //若整除則此數字絕對不是質數
        cout<<"NO\n";
        break; //跳出迴圈
    }
    if(i==n-1){ //若到n-1(也就是迴圈的最後一次) 都沒有跑出去代表他是質數
        cout<<"YES\n";
        break;
    }
}

針對方法一的優化

可以再檢查更少次?降低該方法的時間複雜度?

由於因數性質的關係，所以對於一個數字的檢查，其實只需要從 \(2\) 跑到 \(\sqrt{N}\) 即可。

所以只需要檢查區間 \([2,\sqrt{N}]\) 的數字就好

那我們的寫法會是從 \(2\) 一路跑到 \(\sqrt N\) ，而其中由於小數點常常造成不可預期的錯誤，因此我們的慣用寫法會把根號寫在另外一邊，改成使用平方的。

使用暴力判斷判斷此數字 \(n\) 是否為質數

void isPrime(int n){
    bool flag=1;
    for(int i=2;i*i<=n;i++){ //檢查範圍只需要到根號n
        if(n%i==0){ //若整除則此數字絕對不是質數
            flag=0;
            break;
        }
    }
    if(flag) cout<<"YES\n";
    else cout<<"NO\n";
}

小技巧

在迴圈內請用 \(i\times i \le n\) 而非 \(i < \sqrt{n}+1\)

\(\sqrt{n}\) 容易有浮點數誤差

時間複雜度分析

針對一個數字詢問是否為質數，需要跑 \(2\) 直到 \(\sqrt n\) 因此時間複雜度為 \(O(\sqrt n)\)

倘若今天有多筆詢問呢? 當針對範圍內的數字有多筆詢問時，用一樣的方法容易造成超時。

如果使用的是剛剛的方式，根據我們的時間複雜度分析，會變成

\(Q \cdot \sqrt{N}\)

因此當數字一大時就很容易
Time Limit Exceed

Sieve of Eratosthenes

質數篩法

Sieve of Eratosthenes

也就是建立 "質數表"

想法: 最小的質數開始，所有質數的倍數都一定不是質數
因此我們就先用一個陣列，儲存每個數字是不是質數
一開始先把所有大於1的數字當成質數
再從2依序把所有質數的倍數設成非質數

Sieve of Eratosthenes

演算法步驟

從 \(2\) 開始跑到 \(N\)
判斷當前數字是不是質數 (是否被更改過)
如果是質數(尚未被更改過) 把所有質數的倍數設成非質數(更改)

核心程式碼

//n為會跑到的最大值
bool isprime[1000005]; //紀錄每個數字是否是質數
vector<int> prime; // 儲存範圍內所有的質數
isprime[1]=1; // 1 代表此數字不是質數，否則為 0
//先將所有大於1數字設為質數(0)
 
for(int i=2;i<=n;i++){
    if(!isprime[i]){    //如果為質數
        prime.push_back(i);
        for(long long j=2;i*j<=n;j++){ //記得容易會爆int的話要設long long
            //所有質數的倍數設成非質數
            isprime[i*j] = 1;
        }
    }
}

時間複雜度

vector<int> prime;
void sieve(){
    for(int i=2;i<=n;i++){
        if(!isprime[i]){
            prime.push_back(i); //把質數記錄進質數表裡面
            for(long long j=2;i*j<=n;j++){ //主要迴圈 判定每個非質數
                isprime[i*j] = 1;
            }
        }
    }
}

次數為 \(\frac{n}{2} + \frac{n}{3} + ... + \frac{n}{n}\)
為調和級數 \(= n \log n\)

時間複雜度為 \(O(n \log n)\)

針對質數篩的優化

在內迴圈裡的倍數可以直接從 \(i\) 倍開始
因為小於 \(i\) 的倍數之前都跑過了

vector<int> prime;
void sieve(){
    for(int i=2;i<=n;i++){
        if(!isprime[i]){
            prime.push_back(i);
            for(long long j=i; j*i<=n; j++){  //這裡的j可以直接從i開始
                isprime[j*i] = 1;
            }
        }
    }
}

記得 j 需使用 long long 型態，i * i 可能會到 long long 範圍(\(\ge 2\times 10^9\))

\((\frac{N}{2} - 2) + (\frac{N}{3} - 3) + (\frac{N}{5} - 5) + ... + (\frac{N}{\sqrt{N}} - \sqrt{N})\)

複雜度為 \(O(N\log\log N)\)

質數篩的應用

對於這段程式

vector<int> prime;
bool isprime[N];
void sieve(){
    for(int i=2;i<=n;i++){
        if(!isprime[i]){
            prime.push_back(i);
            for(long long j=i * i; j<=n; j+=i){
                isprime[j] = 1;
            }
        }
    }
}

若我們把第六行的替代的元素換成 \(i\) 是什麼意思呢?

isprime\([i]\) 若等於 \(0\) 代表他是質數，
不等於 \(0\) 則代表其不是質數且 isprime\([i]\) 為 \(i\) 的質因數。

對於每個質數 \(i\) ，設值所有 i 的倍數的 factor 為 i
(需注意 j 的起始值)

void sieve(){
    for(int i=2;i<=n;i++){
        if(!factor[i]){
            prime.push_back(i);
            for(long long j=i; j<=n; j+=i){
                factor[j] = i; //紀錄當前數字i遇到的因數
            }
        }
    }
}

如果我們建好質數表，如果有多筆詢問

每次只要查質數表
就可以直接判斷是不是質數

yeah

質因數分解

那我們有質數表之後，除了判斷一個數字是否為質數外，還可以用來質因數分解。

在質數表內 \(factor[i]\) 的值為 \(i\) 的其中一個質因數，

那我們在質因數分解 \(n\) 的時候，只需要不斷除以 \(factor[n]\) ，並且把中途的數字記錄下來即可。

程式碼實現

void factorize(int x){  //需要質因數分解的數字
    vector<int> factors;
    while(x != 1){
        factors.push_back(factor[x]); //記錄所有因數
        x/=factor[x]; //把他除以自己的因數
    }

    for(int i=0;i<factors.size();i++){  //最後factors裡面即為此數字質因數分解的結果
        cout<<factors[i]<<" ";
    }
}

如果要質因數分解的數字太大?
建表不夠大怎麼辦?

由小到大枚舉質數表內的質數，過程中判斷當前質數是否 \(\le\sqrt{n}\)，
整除時代表此數字為因數，把此數字記錄下來並除掉。

程式碼實現

void factorize(int x){
    vector<int> factors; //質因數分解的答案存在這
    //for 迴圈判斷當前遍歷到的質數還在範圍裡
    for(int i = 0; i < primeSize && prime[i] * prime[i] <= x; i++){ 
      while(x % prime[i] == 0)  //若當前枚舉到的質數是此數的因數
        factors.push_back(prime[i]), x/=prime[i]; //紀錄答案並更新 x
    }
    if(x > 1) factors.push_back(x); //最後記得把自己加進去，若他本身是很大的質數則有可能沒算到

    for(int i=0;i<factors.size();i++) //遍歷並輸出答案
        cout<<factors[i]<<" ";
}

兩種質因數分解分析

• 範圍問題

  • 第一種方法: 由於會戳到 \(factor[x]\) ， 因此 \(x\) 的範圍需小於質數表大小
  • 第二種方法: 能分解的範圍到 \(prime[i]\times prime[i]\)，因此值域上可以處理到 \(N\times N\) (\(N\)為質數表的範圍)

• 時間複雜度分析

  • 第一種方法: 複雜度由質因數數量決定，最差的情況是所有質因數都是 \(2\) (最小的質因數)，因此時間複雜度為 \(O(\log x)\)
  • 第二種方法: \(O(\sqrt x)\)

針對以上兩種分析就可以看出這兩種方法的優劣以及該如何選擇

之後會上到更快搜尋質數的方法

能處理更大範圍 (\(10^{18}\)) 的質數問題

miller-rabin 有興趣再自己去看

補充

一個數字 \(n\) 的因數的數量最多只有 \(n^{\frac{1}{3}}\) 個

當題目需要枚舉因數時，如果要判斷因數數量有多少，可以用 \(n^{\frac{1}{3}}\) 當成上界來分析複雜度。

練習時間&&本週題單

https://vjudge.net/contest/661539