<style> .reveal .slides { text-align: left; font-size:36px; } .cpp { font-size: 32px !important; line-height: 36px !important; } </style> # pretrain 1 2023 Introduction to Competitive Programming 2022/12/01 ---- ## 自我介紹 李欣祐 LeeShoW <div style="font-size: 30px"> * APCS 5/5 * CPE 七題 * 校內海洋盃第二 * 2022北區大專初級組第一名 </div> ---- ## 自我介紹 賴柏勛 可撥呆呆獸 <div style="font-size: 30px"> * 2022 ICPC 國際大學生程式設計競賽 臺北新竹賽區 銀牌 * CPE 七題 * 校內海洋盃第一 </div> ---- ## 上課模式 <div style="font-size: 30px"> 第一節課上課，大概介紹一下之後上課的模式 ### 課堂上 * 講解演算法 * 實作練習 ### 課後 * 回家練習 </div> ---- <div style="font-size: 30px"> 沒意外這學期固定星期四，地點 212 教室 因為借不到電腦教室所以沒筆電的回去再練習 </div> ---- ## 今天要教的內容 * 時間複雜度 * 質數判斷 * 快速冪 --- # 時間複雜度 - 與**輸入大小**有關的函數 - 用來估計程式執行大約的時間 - 用程式執行次數來去估算執行時間 - 通常以大 $O$ 符號表式，ex: $O(N)$、$O(NlgM)、O(k^3)$ ---- ### 計算大概的執行次數 執行次數無法完全精準的計算 可能受到編譯器優化影響 使得執行次數不是我們所計算的 而只需要計算大概的次數就可以去估算時間 ---- ### 表達時間複雜度 - 以大$O$符號表示，其中大$O$符號代表"上限"的意思 - 以$T(N)$代表時間複雜度函數($N$是輸入大小) - 舉例:$T(N)=O(N^2), T(N,Q)=O(Q\times2^N),\\T(S,w)=O(Slgw), T(N)=O(1)$  ---- ### 計算時間複雜度 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(lgn)$ 在算複雜度時，通常 $lg$、$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}{4}+...\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的程式 - 在比賽中更容易作時間分配、難度分析 --- # 判斷質數 ---- <div style="font-size: 30px"> $Q$ 筆詢問 每筆詢問給你一個數字 $N$，判斷是不是質數? 質數: 除了 $1$ 跟 $N$ 都不是 $N$ 的因數 TimeLimit : 1 second * subtask 1: $Q=1, N=10^6$ * subtask 2: $Q=1, N=10^{12}$ * subtask 3: $Q=10^6, N=10^{6}$ * ~~subtask 4: $Q=10^5, N=10^{18}$~~ </div> ---- ### subtask 1: $Q=1, N=10^6$ <div style="font-size: 30px"> 窮舉每個小於 $N$ 的數字，判斷有沒有整除 $N$ 整除代表是 $N$ 的因數 7 -> 2, 3, 4, 5, 6 無其他因數 25 -> 2, 3, 4, 5 為因數 120 -> 2 為因數 最差情況 : 判斷的數字是質數，因此要跑 $N-2$ 個數字 (除了 $1$ 跟 $N$ ) </div> ---- ### subtask 1: $Q=1, N=10^6$ <div style="font-size: 30px"> 可以再檢查更少次? 最差情況跑到 $N/2$ 就好 在小於 $N$ 的數字中，如果數字 $x$ 大於 N/2 則不可能是 $N$ 的因數 所以只需要檢查區間 $[2,N/2]$ 的數字就好 </div> ---- ### subtask 2: $Q=1, N=10^{12}$ <div style="font-size: 30px"> 如果用剛剛說的方法做，最差情況要跑到 $N/2$ 但 1 秒跑得完嗎? </div> ---- ### subtask 2: $Q=1, N=10^{12}$ <div style="font-size: 30px"> 1 秒電腦可以跑的運算量約為 $5 \cdot 10^8$ 如果用前面說的方法 運算量最差約為 $\frac{10^{12}}{2} = 5 \cdot 10^{11}$ $5 \cdot 10^{11} > 5 \cdot 10^8 \to$ TLE ( Time Limit Exceed ) 還不夠快 QQ </div> ---- ### subtask 2: $Q=1, N=10^{12}$ <div style="font-size: 30px"> 先來觀察以下數字 $12 = 1 \times 12 = 2 \times 6 = 3 \times 4 = 4 \times 3 = 6 \times 2 = 12 \times 1$ $9 = 1 \times 9 = 3 \times 3 = 9 \times 1$ $7 = 1 \times 7 = 7 \times 1$ 如果一個數字 $x$ 是 $N$ 的 因數則 $x$ 或者 $N/x$ 必定有一個 $\le \sqrt{N}$ </div> ---- ### subtask 2: $Q=1, N=10^{12}$ <div style="font-size: 30px"> 因此我們只需要跑到 $\sqrt{N}$ 就好 如果在$\le \sqrt{N}$ 的範圍沒檢查到因數 則後面不會有 $N$ 的因數 $\sqrt{10^{12}} = 10^6 < 5 \cdot 10^8(1秒)$ </div> ---- ### subtask 3: $Q=10^6, N=10^{6}$ <div style="font-size: 30px"> 用剛剛的方法? 每筆詢問最差跑 $10^3$ 的運算量 有 $10^6$ 筆詢問 $Q \cdot \sqrt{N} = 10^{9} > 5 \cdot 10^8$ ( 1秒 ) Time Limit Exceed </div> ---- ## Sieve of Eratosthenes ## 質數篩法 ---- ## Sieve of Eratosthenes <div style="font-size: 30px"> 建立質數表 想法: 最小的質數開始，所有質數的倍數都一定不是質數 因此我們就先用一個陣列，儲存每個數字是不是質數 一開始先把所有大於1的數字當成質數 再從2依序把所有質數的倍數設成非質數 </div> ---- ## Sieve of Eratosthenes  ---- <div style="font-size: 30px"> ## 演算法步驟 從 2 開始跑到 N 判斷當前數字是不是質數 如果是質數把所有質數的倍數設成非質數 </div> ---- ## 核心程式碼 ```cpp= bool isprime[1000005]; int primeSize = 0, prime[200005]; //先將所有大於1數字設為質數 for(int i=2;i<=n;i++) isprime[i] = 1; for(int i=2;i<=n;i++){ if(isprime[i]){ //如果為質數 prime[primeSize++] = i; for(long long j=2;i*j<=n;j++){ //所有質數的倍數設成非質數 isprime[i*j] = 0; } } } ``` ---- ## 執行次數 <div style="font-size: 30px"> 將所有數字設成 質數 ```cpp= for(int i=2;i<=n;i++) isprime[i] = 1; ``` 約n次 ```cpp= for(int i=2;i<=n;i++){ if(isprime[i]){ prime[primeSize++] = i; for(long long j=2;i*j<=n;j++){ isprime[i*j] = 0; } } } ``` 次數為 $\frac{n}{2} + \frac{n}{3} + ... + \frac{n}{n}$ 為調和級數 $= n lg n$ </div> ---- ## 優化 <div style="font-size: 30px"> 在內迴圈裡的倍數可以直接從 i 倍開始 因為小於 i 的倍數之前都跑過了 ```cpp= for(int i=2;i<=n;i++){ if(isprime[i]){ prime[primeSize++] = i; for(long long j=i; i*j<=n; j++){ isprime[i*j] = 0; } } } ``` 複雜度為 $O(NloglogN)$ ---- <div style="font-size: 30px"> 回到原本問題 * subtask 3: $Q=10^6, N=10^{6}$ 如果我們建好質數表，每次只要查質數表 就可以直接判斷是不是質數 執行次數約為 $Q \cdot 1 = 10^6 < 5 \cdot 10^8$ </div> ---- ### ~~subtask 4: $Q=10^5, N=10^{18}$~~ miller-rabin 有興趣再自己去看 --- ## 補充 因數的數量最多只有 $n^{\frac{1}{3}}$ 個 --- # 快速冪 ---- <div style="font-size: 30px"> 先把 y 換成二進位 以 $2^{13}$ 為例 $13$ $= 1101$ $= 1\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0$ $= 8 + 4 + 1$ $\to 2^{13} = 2^8 * 2^4 * 2^1$ </div> ---- 因此，我們只要求出 $2^8, 2^4, 2^1$ 就好 也就是 $lgN$ 次 ---- ## 實作 <div style="font-size: 30px"> 一樣以2^13為例 1101 就從最右邊的開始做 判斷最右邊的bit是不是1如果是1則把答案乘上去 並且每次把 x 平方 接著把整個右移一個，變成 110 因此一樣變成判斷最右邊的bit即可 $再右移\to 11$ $再右移\to 1$ 一直做到 y 右移到 0 為止 </div> ---- ## 過程 <div style="font-size: 25px"> | x | y | 原本答案 | 計算後答案 | | -------- | -------- | -------- | -------- | | $2^1$ | 1101 | $2^0$ | $2^1$ | | $2^2$ | 110 | $2^1$ | $2^1$ | | $2^4$ | 11 | $2^1$ | $2^5$ | | $2^8$ | 1 | $2^5$ | $2^{13}$ | </div> ---- ## 程式碼 ```cpp= long long mypow(long long x,long long y){ long long ans = 1; while(y){ if( y&1 ) ans = ans * x % p; x = x * x % p; //每次把自己平方 y >>= 1; //每次右移一格 } return ans; } ``` ---- 換成2進位，只需要計算 $lgN$ 次 $lg10^{18} = 60 < 5 \cdot 10^8$ --- ## 練習時間 :) 問啥都行 題單：https://vjudge.net/group/ntou_cse107?r=wG5DBzKmcopmEWn7sqQn