or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
競賽基本知識
Wiwi Ho
tags:
CRC
https://hackmd.io/@wiwiho/crc1082algo

複雜度分析
什麼是複雜度?
有一個函數 \(f(n)\)
它的值跟 \(n\) 有什麼關係?
\(f(n)=n^2+2n-1\)
\(n^2\) 對 \(f(n)\) 的值影響最大
\(\Rightarrow\) \(f(n) \in O(n^2)\)
Big-O notation
對於兩個函數 \(f(n)\) 和 \(g(n)\)
若存在正數 \(c\) 和 \(n_0\)
滿足所有的 \(n \geq n_0\) 都符合 \(f(n) \leq cg(n)\)
則 \(f(n) \in O(g(n))\)
複雜度怎麼求
只留最高次項
且把係數拿掉
比大小
複雜度越大
表示函數值成長越快
怎麼比(嚴謹定義)
\(\lim_{n \to \infty} \frac{g(x)}{f(x)}\)
如果 \(O(g(n))>O(f(n))\)
\(O(f(n)) \in O(g(n))\)
\(\Rightarrow 2n^2+n-1 \in O(2n^2+n-1) \in O(n^2) \in O(n^3)\)
複雜度非唯一
通常會選最小而且寫出來最簡單的
用詞
常數:\(O(1)\)
線性:\(O(n)\)
其他應該很好懂 (?
e.g. 對數(\(O(\log n)\))、根號(\(\sqrt{n}\))……
STL 的複雜度
查表
cppreference.com
時間複雜度
表示程式的執行時間如何隨輸入的數值成長
\(\Rightarrow\) 用來比較演算法好壞的方法
會用多少時間?
不能準確計算
把所有參數的最大值代入後
約 \(10^8\) 到 \(10^9\) 為一秒
範例
常數
被丟掉的常數
常數重要嗎?
當然重要!
時間複雜度 \(O(n^2)\)
如果 \(n \leq 10000\)
\(n^2=10^8\)
好像勉強還行?
那個 10 呢?
\(10n^2=10^9\)
可能不太行
如果常數會造成時間剛好超過
那就很重要
看不到的常數
加、減、乘、除、模都是 \(O(1)\)
但除和模需要比較多時間
unordered_set、unordered_map
的插入刪除尋找都是 \(O(1)\)
但常數很大
輸入輸出
各種流
輸入流、輸出流?
什麼是流?
輸出流:把東西給它,它會負責輸出到某地方
輸入流:跟它要一個東西,它會負責從某個地方拿給你
標準流
預設:在 terminal 輸入輸出
可以重新導向成在檔案輸入輸出
錯誤流
一種輸出流
用來輸出錯誤訊息
不會被 judge 讀到
重新導向
在程式碼
在 terminal
緩衝區
cin
輸入的東西先到緩衝區
程式讀取的時候會從緩衝區拿資料
cout
輸出的東西先到緩衝區
flush 後再真的輸出到它該去的地方
cerr
沒有緩衝區
會馬上輸出到它該去的地方
stringstream
一種 iostream
\(\Rightarrow\) 是輸入流也是輸出流
輸入輸出優化
效率太差?
來看看它為什麼差
輸出到 terminal 或檔案裡的常數很大
cout 自動 flush
歷史因素
要和 scanf/printf 同步
ios_base::sync_with_stdio(false)
運算子重載
輸入格式
EOF
EOF = End Of Line
某些題目:
一個檔案有多筆測資
而且不告訴你有幾筆
terminal 不是 file?
按 ctrl+z 或 ctrl+d 製造 EOF
輸入一整行
跟 >> 混用
預期:a=abc,b=abcd abcd 實際:a=abc,b=空字串
多 getline 一次
忽略輸入
ZJ c268:
給你一堆數字,找三個數字當三角形邊長
\(O(n \log n)\) 可以嗎?
\(n \leq 10^7\)
太多了吧
\(n \geq 50\) 保證有解
所以超過 50 項就可以不用讀了
可是一個檔案多測資,怎麼辦?
把輸入忽略掉
輸出格式
小數位數
數字寬度
前置處理器
什麼是前置處理器?
在編譯之前,會先做前置處理
都是前置處理器的指令
什麼是前置處理?
根據指令修改程式碼
include
把別的檔案的內容在該處貼上
引號、角括號?
找檔案的地方不同
define
macro/ 巨集 / 宏
把所有單字 a 換成 b
也可以用 function
換行
一樣嗎?
條件判斷
符合條件的地方才會留下來
判斷 a 有沒有被 define 過
去寫練習題