#学习自用#
算法性能分析
时间复杂度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;
}
else
CarryBit = 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();
else
return 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;
}
