时间复杂度计算法方法
算法的稳定性：如果排序后，两个拥有相等关键字的元素a和b的相对位置没有发生变换，则稳定，否则不稳定。
内部排序是指在排序期间元素全部存放在内存中的排序；外部排序是指在排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断地在内、外存之间移动的操作。
然后再来温习一下时间复杂度的计算：
时间复杂度的计算其实就是计算出算法某条执行语句的具体执行频度，之后取频度的数量级即可。下面用例子温习：
例1：
void fun(int n){
int i = 1;
while(i<n) i*=2;
}
设语句 i*=2运行t次，则，t=maxtt,s.t.2t<n，即t是使2^t<n成立最大的t。故t=log2n(向下取整）。故时间复杂度O(log2 n)。
例2：
count=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j++)
count++;
外循环t次，2^t=n，t=log2 n。内循环n次。故O(nlog2n)。
例3：
y=0;
while((y+1)(y+1)<=n)
y+=1;
\(t=max_t t , s.t. t^2<=n\)
t=n(1/2)。O(n0.5)。
例4：
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int k=1;k<=j;k++)
x++;
内层循环受外循环控制变量大小控制，故不能简单相乘。研究发现，i=某值c时，最内层循环次数为：1+2+…+c。故\(O(\sum_i^n i*(n-i-1))\)但不会算，不过有个结论可以用：\(\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j l=O(\frac{n^3}{6})=O(n^3)\)
另外总结一些常用数学公式：
等差数列求和公式：\(Sn = \frac{a_1+a_n}{2}n=a_1n+\frac{n(n-1)}{2}d\)
等比数列求和公式：\(Sn = a_1\frac{1-q^n}{1-q}\)
和公式：\(1+2+…+n=\frac{n(n+1)}{2}\)
平方和公式：\(1^2+2^2+…+n^2=\frac{n(n+1)(2n+1)}{6}\)
立方和公式：\(1^3+2^3+…+n^3=\frac{n^2(n+1)^2}{4}=(\frac{n(n+1)}{2})^2\)