### 競賽程式導論 程式競賽中時間寶貴，執行時間越短越好。所以要減少所花費的時間，以及估算程式的執行時間 ---- ### 競賽程式先備知識 * 時間複雜度 * 前綴和&差分 * $overflow-rounding$ $error$ * $I/O$優化 --- ## 複雜度估算 為了評估程式的執行效率，我們可以測量時間 ---- 複雜度通常以$O(f(n))$表示 O通常被稱為大O符號，$n$是資料量，而$f(n)$是$n$的函數 ---- * 時間複雜度 | Big O Notation | 別名 | 常見演算法 | | -------- | -------- | -------- | | $O(1)$ | 常數 | 陣列讀取 | | $O(n)$ | 線性 | [Linear search](https://en.wikipedia.org/wiki/Linear_search)| | $O(logn)$ | 對數(Logarithmic ) | [二分搜尋法](https://en.wikipedia.org/wiki/Binary_search_algorithm)| | $O(nlogn)$ | 線性 | [堆積排序](https://hackmd.io/@SupportCoding/Heap_sort)，[合併排序](/Merge_sort) | ---- | Big O Notation | 別名 | 常見演算法 | | -------- | -------- | -------- | | $O(n^2)$ | 平方 | [氣泡排序](https://en.wikipedia.org/wiki/Bubble_sort)，[插入排序](https://en.wikipedia.org/wiki/Insertion_sort)| | $O(n^3)$ | 三次方 | 三重迴圈枚舉法，高斯消去法求解線性方程組 | | $O(2^n)$ | 指數 | 費氏數列 | | $O(n!)$ | 階層 | 排列組合，八皇后問題 | ----  ---- 根據上圖 我們要盡可能避免使用$n^2, n^3, 2^n$ 這三個 增長速度飛快的方法來執行 ---- 通常一秒能執行的量大概是$O(10^9)$ 因此我們可以得到下表 ---- | $n$大小 | 通常使用甚麼方法 | | -------- | -------- | | $n>10000$ | $O(n)$ or $O(nlog(n))$| | $n>1000$ | $O(n^2)$ | | $n>100$ | $O(n^3)$ | | $20<=n<=26$ | $O(2^n)$ | | $n=<10$ | $O(n!)$ | --- ## 前綴和$prefix-sum$ $ps[i]$=$\sum_{n=0}^{i} val[n]$ $ps[x]-ps[y]$=$\sum_{n=y+1}^{x} val[n]$ ```cpp= //一般的前綴和陣列的建立 int val[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; //前墜和(ps)陣列可以方便找區間和 int ps[10] = {0}; ps[0] = val[0]; //預處理第一項 for(int i = 1;i < 10;i++) { ps[i]=ps[i-1]+val[i]; } //前綴和陣列的第n項=前綴和陣列的前項+原陣列的第n項 ``` ---- ### 差分 $d[i]=val[i]-val[i-1] ; d[1]=val[1]$ ```cpp= int val[3] = {3, 3, 4}; int ps[3] = {3, 6, 10}; //前綴和陣列 //對ps進行差分 int d[3]= {3, ps[1]-ps[0], ps[2]-ps[1]} //變成原陣列 ``` ---- 可得  ---- ### 前綴和與插分的進階技巧 EX：給定一陣列$A_{1},A_{2}...A_{n}$ 進行$i$次, 每次給$l, r, x$ 代表$from$ $A_{l}$ $to$ $A_{r}, all+=x$ 求最後的陣列 若正常做所需時間=$O((l-r)*x)$ 容易TLE ---- 因此我們可以對差分陣列進行改變 ```cpp int val[5] = {3, 4, 5, 6, 7}; int d[5] = {3, 1, 1, 1, 1}; ``` 若要改變的區間是$val[1]～val[3], +=3$ 我們可以改成將$d[1]+3, d[3+1]-3$ ```cpp d[5] = {3, 4, 1, 1, -2} //進行前綴和 val={3, 3+4, 3+4+1, 3+4+1+1, 3+4+1+1-2} ``` 這樣可以把$O(n)$變成$O(1)$ --- #### $overflow$ $overflow$是C++數字的存儲上限 | $int$ | $long-long$ | | -------- | -------- | | $2^{32}-1$約$10^9$ | $2^{64}-1$ 約$10^{18}$ | 如果使用該資料類型卻超過,會產生亂數 ---- #### $rounding-error$ C++中浮點數可能會產生存儲誤差 例如0.3在二進制就是無限小數,導致無法存儲 出現誤差 --- ## $I/O$優化 C++中如果使用`cin和cout`,時間常數比較大 即花費較多時間 可以改用`scanf和printf`或進行$I/O$優化,減少時間 ```cpp= //加上這行即可I/o優化 ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); ``` --- # 結束!!!