<style> .reveal .slides { text-align: left; font-size:30px; } </style> # 複雜度分析 & 質數判定 ---- - 複雜度分析 (Time Complexity) - 質數判定 (Primality Test) --- ## 時間複雜度 ### Time Complexity - 與**輸入大小**有關的函數 - 可以用來估計程式執行大約的時間 - 用程式執行次數來去估算執行時間 - 通常以大 $O$ 符號表式，ex: $O(N)$、$O(N\log M)、O(k^3)$ ---- ### 計算大概的執行次數 執行次數無法完全精準的計算 可能受到編譯器優化影響 使得執行次數不是我們所計算的 而只需要計算大概的次數就可以去估算時間 ---- ### 表達時間複雜度 - 以大$O$符號表示，其中大$O$符號代表 "上限" 的意思 ---- ### 計算時間複雜度 1. 估計程式的運算執行次數 2. 將得到的函數最高階項以外的項全部刪掉 3. 把係數拿掉 ---- ### 迴圈的時間複雜度 迴圈的執行次數\*每次迴圈的時間複雜度 ---- ```cpp for(int i=0;i<n;i++) { arr[i]=arr[i-1]*a+b; //O(1) swap(a,b); //O(1) } ``` $O(n)$ ---- ```cpp 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)$ ---- ```cpp 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) ... ---- ### 實作範例分析 1. ```cpp for(int i=100000;i<n;i++) { for(int j=i-100;j>=1000;j--) cout<<i<<" "<<j<<'\n'; } ``` ---- 1. ```cpp for(int i=10;i<n;i++) { for(int j=i-100;j>=1000;j--) cout<<i<<" "<<j<<'\n'; } ``` $O(n^2)$ ---- 2. ```cpp for(int i=0;i<100000000;i++) cin>>n,cout<<n*n<<'\n'; ``` ---- 2. ```cpp for(int i=0;i<100000000;i++) cin>>n,cout<<n*n<<'\n'; ``` $O(1)$ ---- 3. ```cpp for(int i=1;i<=n;i++){ sort(arr,arr+i); } ``` ---- 3. ```cpp for(int i=1;i<=n;i++){ sort(arr,arr+i); } ``` $O(n^2lgn)$ $(\sum\limits_{k=1}^{n}klgk\approx n^2lgn)$ ---- 4. ```cpp for(int i=1;i<n;i=i*2){ for(int j=i;j<n;j+=i) arr[j]+=arr[j-i]; } ``` ---- 4. ```cpp 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)$ ---- 5. ```cpp void f(int n) { if(n==0) return 1; return f(n-1)*n; } ``` ---- 5. ```cpp void f(int n) { if(n==0) return 1; return f(n-1)*n; } ``` $O(n)$ ---- 6. ```cpp 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); } ``` ---- 6. ```cpp 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$ ) ---- 簡單的快速判斷，暴力跑過每個數字 ```cpp 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$ 是否為質數 ```cpp 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$ 判斷當前數字是不是質數 (是否被更改過) 如果是質數(尚未被更改過) 把所有質數的倍數設成非質數(更改) ---- ## 核心程式碼 ```cpp= //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; } } } ``` ---- ## 時間複雜度 ```cpp= 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$ 的倍數之前都跑過了 ```cpp= 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)$ ---- ## 質數篩的應用 對於這段程式 ```cpp= 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 的起始值) ```cpp= 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 :bread: ---- ## 質因數分解 那我們有質數表之後，除了判斷一個數字是否為質數外，還可以用來質因數分解。 ---- 在質數表內 $factor[i]$ 的值為 $i$ 的其中一個質因數， 那我們在質因數分解 $n$ 的時候，只需要不斷除以 $factor[n]$ ，並且把中途的數字記錄下來即可。 ---- ## 程式碼實現 ```cpp 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}$， 整除時代表此數字為因數，把此數字記錄下來並除掉。 ## 程式碼實現 ```cpp 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