定期推送账号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，融科教育信息学竞赛培训等诸多优质内容的微信平台，欢迎分享文章给你的朋友或者朋友圈！
算法分析
算法分析的目的是预测算法所需的资源，如计算时间（CPU 消耗）、内存空间（RAM 消耗）、通信时间（带宽消耗）等，以及预测算法的运行时间，即在给定输入规模时，所执行的基本操作数量，或者称为算法复杂度。
算法的运行时间取决于输入的数据特征，输入数据的规模和运行时间的上限（因为运行时间的上限是对使用者的承诺）。算法分析一般忽略掉那些依赖于机器的常量，而关注运行时间的增长趋势。一般仅考量算法在最坏情况下的运行情况，使用 O 记号法表示最坏运行情况的上界。例如：
线性复杂度O(n) 表示每个元素都要被处理一次。
平方复杂度 O(n2)表示每个元素都要被处理 n 次。
复杂度
标记符号
描述
常量（Constant）
O(1)
操作的数量为常数，与输入的数据的规模无关。
对数（Logarithmic）
O(log2n)
操作的数量与输入数据的规模 n 的比例是 log2 (n)。
线性（Linear）
O(n)
操作的数量与输入数据的规模 n 成正比。
平方（Quadratic）
O(n2)
操作的数量与输入数据的规模 n 的比例为二次平方。
立方（Cubic）
O(n3)
操作的数量与输入数据的规模 n 的比例为三次方。
指数（Exponential）
O(2n)
O(kn)
O(n!)
指数级的操作，快速的增长。
不同时间复杂度中元素数量与操作次数的关系图：
而通常时间复杂度与运行时间有一些常见的比例关系：
复杂度
10
20
50
100
1000
10000
100000
O(1)
O(log2(n))
O(n)
O(n*log2(n))
O(n2)
2s
3-4 min
O(n3)
20s
5 hours
231 days
O(2n)
260 days
hangs
hangs
hangs
hangs
O(n!)
hangs
hangs
hangs
hangs
hangs
hangs
O(nn)
3-4 min
hangs
hangs
hangs
hangs
hangs
hangs
计算代码块的渐进运行时间，即算法复杂度的方法有如下步骤：
1、确定决定算法运行时间的组成步骤。
2、找到执行该步骤的代码，标记为 1。
3、查看标记为 1 的代码的下一行代码。如果下一行代码是一个循环，则将标记 1 修改为 1 倍于循环的次数 1 * n。如果包含多个嵌套的循环，则将继续计算倍数，例如 1 * n * m。
4、找到标记到的最大的值，就是运行时间的最大值，即算法复杂度描述的上界。
如，斐波那契数列：
Fib(0) = 0，Fib(1)= 1，Fib(n) = Fib(n-1) + Fib(n-2)
F() = 0, 1, 1, 2, 3,5, 8, 13, 21, 34 ...
例1
int Fibonacci(int n)
{
if (n
return n;
else
return Fibonacci(n - 1) + Fibonacci(n -2);
}
这里，给定规模 n，计算Fib(n) 所需的时间为计算 Fib(n-1) 的时间和计算 Fib(n-2) 的时间的和。T(n，T(n)= T(n-1) + T(n-2) + O(1)，通过使用递归树的结构描述可知算法复杂度为 O(2n)。
例2
int Fibonacci(int n)
{
if (n
return n;
else
{
int[] f = new int[n + 1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i
{
f[i] = f[i - 1] + f[i - 2];
}
returnf[n];
}
}
同样是斐波那契数列，我们使用数组 f 来存储计算结果，这样算法复杂度优化为 O(n)。
例3
int Fibonacci(int n)
{
if (n
return n;
else
{
int iter1 = 0;
int iter2 = 1;
int f = 0;
for (int i = 2; i
{
f = iter1 + iter2;
iter1 = iter2;
iter2 = f;
}
return f;
}
}
同样是斐波那契数列，由于实际只有前两个计算结果有用，我们可以使用中间变量来存储，这样就不用创建数组以节省空间。同样算法复杂度优化为 O(n)。
例4
通过使用矩阵乘方的算法来优化斐波那契数列算法。
static intFibonacci(int n)
{
if (n
return n;
int[,] f = { { 1, 1 }, { 1, 0 } };
Power(f, n - 1);
return f[0, 0];
}
static voidPower(int[,] f, int n)
{
if (n
return;
int[,] m = { { 1, 1 }, { 1, 0 } };
Power(f, n / 2);
Multiply(f, f);
if (n % 2 != 0)
Multiply(f, m);
}
static voidMultiply(int[,] f, int[,] m)
{
int x = f[0, 0] * m[0, 0] + f[0, 1] *m[1, 0];
int y = f[0, 0] * m[0, 1] + f[0, 1] *m[1, 1];
int z = f[1, 0] * m[0, 0] + f[1, 1] * m[1,0];
int w = f[1, 0] * m[0, 1] + f[1, 1] *m[1, 1];
f[0, 0] = x;
f[0, 1] = y;
f[1, 0] = z;
f[1, 1] = w;
}
优化之后算法复杂度为O(log2n)。
排序算法
1、快速排序
#include
inline void Rd(int&res){
res=0;char c;
while(c=getchar(),c
dores=(res
while(c=getchar(),c>47);
}
int res[100005];
void qsort(int L,intR){
if(L>=R)return;
int key=res[L],low=L,high=R;
while(low
while(low
if(low
while(low=res[low])++low;
if(low
}
res[low]=key;
qsort(L,low-1),qsort(low+1,R);
}
int main(){
int n;Rd(n);
for(int i=1;i
qsort(1,n);
for(int i=1;i
printf('%d%c',res[i],i==n?'\n':' ');
}
2、归并排序
#include
inline void Rd(int&res){
res=0;char c;short f=1;
while(c=getchar(),c
do if(c=='-')f=-1;
elseres=(res
while(c=getchar(),c>47);
res*=f;
}
const int M=1000005;
int a[M],b[M];
void Merge(int L,intR){
if(L==R)return;
int mid=L+R>>1;
Merge(L,mid);Merge(mid+1,R);
int low=L,high=mid+1,c=L;
while(low
if(a[low]
else b[c++]=a[high++];
while(low
while(high
for(int i=L;i
}
int main(){
int n;Rd(n);
for(int i=1;i
Merge(1,n);
for(int i=1;i
printf('%d%c',a[i],i==n?'\n':' ');
}
3、堆排序
#include
inline void Rd(int&res){
res=0;char c;
while(c=getchar(),c
dores=(res
while(c=getchar(),c>47);
}
struct Heap{
static const int M=100005;
int heap[M],sz;
Heap(){sz=0;}
inline void swap(int *a,int *b){
if(a==b)return;
int t=*a;*a=*b;*b=t;
}
int top(){return heap[1];}
void push(int val){
heap[++sz]=val;
int pos=sz;
while(pos>>1){
int nxt=pos>>1;
if(heap[nxt]>heap[pos])swap(&heap[nxt],&heap[pos]);
else break;
pos=nxt;
}
}
void pop(){
int pos=1;
heap[pos]=heap[sz--];
while((pos
int nxt=pos
if(nxt+1
if(heap[nxt]
else break;
pos=nxt;
}
}
}q;
int main(){
int n;Rd(n);
for(int i=1,x;i
for(int i=1;i
printf('%d',q.top());
putchar(i==n?'\n':' ');
q.pop();
}
}
4、基数排序
#include
inline void Rd(int&res){
res=0;char c;
while(c=getchar(),c
dores=(res
while(c=getchar(),c>47);
}
static const intM=100005,S=10;
inta[M],s[S][M],sz[S];
int main(){
int n;Rd(n);
for(int i=1;i
for(int base=1,i=1;i
for(int j=0;j
for(int j=1;j
int step=a[j]/base%10;
s[step][++sz[step]]=a[j];
}
int tot=0;
for(int j=0;j
for(int k=1;k
a[++tot]=s[j][k];
}
for(int i=1;i
printf('%d%c',a[i],i==n?'\n':' ');
}
长沙信息学竞赛
