與輸入大小有關的函數
可以用來估計程式執行大約的時間
用程式執行次數來去估算執行時間
通常以大 \(O\) 符號表式,ex: \(O(N)\)、\(O(N\log M)、O(k^3)\)
執行次數無法完全精準的計算
可能受到編譯器優化影響
使得執行次數不是我們所計算的
而只需要計算大概的次數就可以去估算時間
迴圈的執行次數*每次迴圈的時間複雜度
for(int i=0;i<n;i++)
{
arr[i]=arr[i-1]*a+b; //O(1)
swap(a,b); //O(1)
}
\(O(n)\)
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)\)
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\)
其實從函數的功能應該可以猜出其複雜度
不然的話就把它記起來(至少常用的函數要知道)
例:memset O(N)、 sort O(NlgN)、 __gcd O(lgN)、lower_bound O(lgN) …
for(int i=100000;i<n;i++)
{
for(int j=i-100;j>=1000;j--)
cout<<i<<" "<<j<<'\n';
}
for(int i=10;i<n;i++)
{
for(int j=i-100;j>=1000;j--)
cout<<i<<" "<<j<<'\n';
}
\(O(n^2)\)
for(int i=0;i<100000000;i++)
cin>>n,cout<<n*n<<'\n';
for(int i=0;i<100000000;i++)
cin>>n,cout<<n*n<<'\n';
\(O(1)\)
for(int i=1;i<=n;i++){
sort(arr,arr+i);
}
for(int i=1;i<=n;i++){
sort(arr,arr+i);
}
\(O(n^2lgn)\) \((\sum\limits_{k=1}^{n}klgk\approx n^2lgn)\)
for(int i=1;i<n;i=i*2){
for(int j=i;j<n;j+=i)
arr[j]+=arr[j-i];
}
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)\)
void f(int n)
{
if(n==0) return 1;
return f(n-1)*n;
}
void f(int n)
{
if(n==0) return 1;
return f(n-1)*n;
}
\(O(n)\)
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);
}
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)\)
把時間複雜度的大\(O\)符號拿掉,並將題目給定的輸入範圍上限帶入函數,令得到的數值為 \(T\)
一般而言假設c++每秒能跑 \(10^8\) 的數量級
假設題目的時限是TL秒,那麼
當你想到一個做法後,在開始寫之前就能先用時間複雜度來判斷是否會 TLE,以避免浪費時間在寫必然會 TLE 的程式
在比賽中更容易作時間分配、難度分析
對於範圍內的數字使用快速的方法判斷它是否為質數。
詢問數字 \(N\) 是否為質數?
窮舉每個小於 \(N\) 的數字,判斷該數字是否整除 \(N\)
若整除代表枚舉的該數字是 \(N\) 的因數
以 \(7\) 為例子,我們要跑一個迴圈從 \(2\) 跑到 \(6\) 並且用每一個數字去除除看。
最差情況 : 判斷的數字是質數,因此要跑 \(2\sim N-1\) 總共 \(N-2\) 個數字 (除了 \(1\) 跟 \(N\) )
簡單的快速判斷,暴力跑過每個數字
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\) 是否為質數
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
也就是建立 "質數表"
想法: 最小的質數開始,所有質數的倍數都一定不是質數
因此我們就先用一個陣列,儲存每個數字是不是質數
一開始先把所有大於1的數字當成質數
再從2依序把所有質數的倍數設成非質數
從 \(2\) 開始跑到 \(N\)
判斷當前數字是不是質數 (是否被更改過)
如果是質數(尚未被更改過) 把所有質數的倍數設成非質數(更改)
//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; } } }
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\) 的倍數之前都跑過了
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)\)
對於這段程式
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 的起始值)
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
那我們有質數表之後,除了判斷一個數字是否為質數外,還可以用來質因數分解。
在質數表內 \(factor[i]\) 的值為 \(i\) 的其中一個質因數,
那我們在質因數分解 \(n\) 的時候,只需要不斷除以 \(factor[n]\) ,並且把中途的數字記錄下來即可。
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}\),
整除時代表此數字為因數,把此數字記錄下來並除掉。
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]<<" ";
}
範圍問題
時間複雜度分析
針對以上兩種分析就可以看出這兩種方法的優劣以及該如何選擇
之後會上到更快搜尋質數的方法
能處理更大範圍 (\(10^{18}\)) 的質數問題
miller-rabin 有興趣再自己去看
一個數字 \(n\) 的因數的數量最多只有 \(n^{\frac{1}{3}}\) 個
當題目需要枚舉因數時,如果要判斷因數數量有多少,可以用 \(n^{\frac{1}{3}}\) 當成上界來分析複雜度。
在解題目前,好好分析複雜度再決定使用什麼演算法來實作,
使用複雜度最好的做法不一定是最佳的,需考慮範圍大小、實作量等