#學習自用#
算法性能分析
時間復雜度O()
時間復雜度就是算法計算的次數。
for(int i=0;i<=n;i++)
{ans++;
}
ans++;這串代碼時間復雜度為O(n)，實際時間復雜度為O(n+1)。如果把i++改為i+=2，時間復雜度仍然為為O(n)，實際時間復雜度變為O(n/2 +1)。時間復雜度比較像極限里面的抓大頭，實際時間復雜度就是字面意思很好理解。
常見的時間復雜度：如果是有限次數的都是O(1)、O(log n)、O(n*log n)、O(n)、O(n^2)、O(n^2)。
空間復雜度
處理算法時，額外產生的空間。
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int j=n-1;j>0;j--){for(int i=0;i<n-1;i++){if(a[i]>a[i+1]){swap(a[i],a[i+1]);
}
}
}在這個冒泡排序算法中，a[i] 是儲存原始數據所需要的數組所以不算在額外空間中，而算法的部分看似沒有額外的變量，實際上是需要一個臨時變量來存儲數據以實現交換的，只需要有限的額外空間，空間復雜度為O(1)。
常見的空間復雜度：O(1)、O(log n)、O(n*log n)
穩定性
通常指的是排序算法的一種特性。在排序算法中，如果兩個相等的元素在排序前后的相對位置保持不變，那么這個算法就是穩定的。
高精度計算
用于處理可能會越界的大數。
高精度加法
這里我們需要用到string和整型數組的特性，string作為字符串變量不管怎么輸入都不會越界，而整型數組可以用每個元素儲存一個數字。
#include<iostream>
#include<string>
using namespace std;
void StrtoInt(const string&s,int* a)
{for (int i = 0; i < s.size(); i++){a[s.size() - 1 - i] = s[i] - '0';//將數字反轉存入數組，目的是將個位對齊。}
}
int main()
{string s1, s2;int a[100] = {}, b[100] = {}, c[100] = {};cin >> s1 >> s2;StrtoInt(s1, a);StrtoInt(s2, b);int la = s1.size(), lb = s2.size();int lc = max(la, lb) + 1;//計算結果可能的最大位數int CarryBit = 0;//設置進位for (int i = 0; i < lc; i++){c[i] = a[i] + b[i]+CarryBit;if (c[i] >= 10){c[i] -= 10;CarryBit = 1;}elseCarryBit = 0;}while (c[lc - 1] == 0 && lc > 1)lc--;for (int i = 0; i < lc; i++){cout << c[lc - 1 - i];}cin.get();
}將字符1賦值給int類型，本質上是把字符1的ASC碼值賦值給變量，得到整型的數字就需要把數字字符與字符0相減。將數字反轉存放是為了使各個數位上的數字對齊，如果不反轉，需要想辦法在數位更低的數組，在其數字最高位前面補零，相當麻煩 。while (c[lc - 1] == 0 && lc > 1)是為了去除前置零，即最高位為0時，將輸出位數減少。
高精度減法
這里依舊使用string與數組的特性。
#include<iostream>
#include<string>
using namespace std;
void StrtoInt(const string&s,int* a)
{for (int i = 0; i < s.size(); i++){a[s.size() - 1 - i] = s[i] - '0';//將數字反轉存入數組，目的是將個位對齊。}
}
bool MyStrcmp(const string& str1,const string& str2)
{if (str1.size() != str2.size())//位數不同return str1.size() > str2.size();elsereturn str1 > str2;//位數相同
}
int main()
{string A, B;int a[100] = {}, b[100] = {}, c[100] = {};cin >> A >> B;if (MyStrcmp(A, B)){StrtoInt(A, a);StrtoInt(B, b);}else{StrtoInt(B, a);StrtoInt(A, b);cout << '-';}//保證更大的數字賦值給數組a//執行減法int lc = max(A.size(), B.size());for (int i = 0; i < lc; i++){if (a[i] - b[i] >= 0)c[i] = a[i] - b[i];else{a[i + 1] -= 1;c[i] = 10 + a[i] - b[i];}}//反轉輸出，去前置零while (c[lc - 1] == 0 && lc > 1)lc--;for (int i = 0; i < lc; i++)cout << c[lc - 1 - i];cin.get();
}與加法不同，減法需要考慮從高位退位，以及相減為負數的情況。相減為負數時，負數的值依舊是大數減去小數，而符號我們可以提前輸出，如果不這樣處理，輸出的高位以及輸出中間都可能出現負數。
不管是加法還是減法都記得把在數組定義時初始化，否則數組中全是一些隨機數，如果被減數與減數位數不同，不將數組初始化，c[i]=a[i]-b[i]運行到隨機數出現的地方出錯。
高精度乘法
#include<iostream>
#include<string>
using namespace std;
void StrtoInt(const string&s,int* a)
{for (int i = 0; i < s.size(); i++){a[s.size() - 1 - i] = s[i] - '0';//將數字反轉存入數組，目的是將個位對齊。}
}
int main()
{string A, B;int a[100] = {}, b[100] = {}, c[100] = {};cin >> A >> B;StrtoInt(A, a);StrtoInt(B, b);int la = A.size(), lb = B.size(),lc=la+lb;for(int j=0;j<lb;j++)for (int i = 0; i < la; i++){c[i + j] += a[i] * b[j];}for (int i = 0; i < lc - 1; i++){c[i + 1] += (c[i] / 10);c[i] %= 10;}while (c[lc - 1] == 0 && lc > 1)lc--;for (int i = 0; i < lc; i++)cout << c[lc - 1 - i];cin.get();
}高精度乘法的關鍵是確定相乘后最多有幾位，這里通過一個例子來理解，結果位數越多代表結果越大，而要得到最大的乘積，兩個乘數也必須是最大的，例如9x9=81，這里乘積的位數是兩個乘數位數之和，通過數學歸納法我們可以知道，乘積的位數最多是兩個乘數位數之和。
高精度除法
準確來說是高精度除以低精度。
#include<iostream>
#include<string>
using namespace std;
void StrtoInt2(const string& s, int* a)
{for (int i = 0; i < s.size(); i++){a[i] = s[i] - '0';}
}
int main()
{string A;int B;int a[100] = {}, c[100] = {};cin >> A;cin >> B;StrtoInt2(A, a);int lc=0;int la = A.size();int temp = 0;//記錄余數for (int i = 0; i < la; i++){c[i]=a[i] / B;temp=(a[i] % B);a[i + 1] += temp * 10;}while (c[lc] == 0 && lc < la)lc++;for (int i = lc; i < la; i++)cout << c[i];cout <<endl<< temp;
}
