Master（
最近做初賽題，發現這些國小數學題真是一個都不會（
發現基本上每年都要考主定理，于是在這裡簡單記錄一下。
主定理主要适用于求解形如下面這個遞歸式的時間複雜度：
\[T(n)=aT(\frac{n}{b})+f(n)
\]
其中參數的含義如下：
\(n\) 是問題規模大小。
\(a\) 是原問題子問題的個數。
\(\dfrac{n}{b}\) 是每個子問題的大小，當然這裡的前提是設所有子問題的大小相等。
\(f(n)\) 是分拆子問題和合并子問題的（時間）複雜度函數。
不過就我做的這幾年的提高組初賽題來看，參數的意義實際上不太考，一般都是直接給出柿子讓你分析時間複雜度。
下面的大小比較都是漸進意義上的。
上式的複雜度分析主要如下列三種情況：
當然也有簡化的版本（不與上面的三種一一對應）：
若 \(f(n) > \Theta(n^{\log_ba})\) 且對于足夠大的 \(n\) 和常數 \(c<1\) 有 \(af(\frac{n}{b}) \le cf(n)\)，那麼 \(T(n) = \Theta(f(n)).\)
若 \(f(n) < \Theta(n^{\log_ba})\)，則 \(T(n) = \Theta(n^{\log_ba}).\)
若 \(f(n) = \Theta(n^{\log_ba}\log^kn)\)，則 \(T(n) = \Theta(n^{\log_ba}\log^{k+1}n)\).
Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
顯然我們每次把一個問題分成兩個子問題，是以 \(a=1,b=2\)，即：
\[T(n)=T(\frac{n}{2})+\Theta(1)
因為 \(\Theta(n^{\log_21}) = \Theta(1)\)，是以複雜度為 \(T(n) = \Theta(n^{\log_21}\log^1n) = \Theta(\log n).\)
和二分查找類似，不過原問題的子問題個數為兩個，故 \(a=2\)，同時合并子問題的時間複雜度為 \(\Theta(n)\)，即：
\[T(n)=2T(\frac{n}{2})+\Theta(n)
因為 \(\Theta(n^{\log_22}) = \Theta(n)\)，是以複雜度為 \(T(n) = \Theta(n\log n).\)
假設某算法的計算時間表示為遞推關系式：
\[T(n) = 2T(\frac{N}{4})+sqrt(n),T(1) = 1.
則算法的時間複雜度為（ ）。
因為 \(\Theta(n^{\log_42}) = \Theta(\sqrt n)\)，是以 \(T(n) = \Theta(\sqrt n \log n).\)
\[T(N) = 2T(\frac{N}{2})+N\log N,T(1) = 1.
因為 \(\Theta(N^{\log_22}) = \Theta(N)\) 且 \(k=1\) 時 \(\Theta(N\log N) = \Theta(N \log^k N)\)，是以 \(T(N) = \Theta(N\log^2N).\)
為了維護 CCF 的知識産權利益，本次比賽簡稱 SCP 第一輪。
\[T(n) = 3T(\frac{n}{2})+\Theta(n),T(1) = \Theta(1).
因為 \(\Theta(n^{\log_23}) > \Theta(n)\)，是以 \(T(n) = \Theta(n^{\log_23}).\)
明天就是 CSP-S1 2021 了，希望各位都 RP++，AK 初賽（
希望我能進複賽（
Do you like WHAT YOU SEE ?