1.时间复杂度

• 推导大O阶
  1.用常数1取代运行时间中的所有加法常数；
  2.在修改后的运行次数函数中，只保留最高阶项；
  3.如果最高阶项存在且不是1，则去除这项的系数。

1.1 常数阶

int n;
scanf("%d",&n);
printf("%d\n",n);

• 算法的执行次数函数f(n) = 3，根据第一步将常数项3改为1，没有最高阶项，时间复杂度为O(1).
• 对于分支结构，无论真假，执行次数都是恒定的，不包含在循环结构中的分支结构时间复杂度均为O(1).

1.2 线性阶

int count = 0;
for(int i=0;i<n;++i){
    printf("%d\n",++count);
}

• 循环体中的代码要执行n次，时间复杂度为O(n).

1.3 对数阶

int count = 0;
for(int i=0;i<n;i*=2){
    printf("%d\n",++count);
}

• i = i*2，则有多少个2相乘后大于n，即2^i = n，得到i = log2n。所以时间复杂度为O(logn).

1.4 平方阶

int count = 0;
for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
        printf("%d\n",++count);
    }
}

• 外部循环体要执行n次内部循环，内部循环是时间复杂度为O(n)的语句，在循环n次，时间复杂度为O(n³)

1.5立方阶

int count = 0;
for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
        for(int k=0;k<n;++k){
            printf("%d\n",++count);
        }
    }
}

• 由于第一层循环以及第二层循环，需要循环n^2次第三层循环语句，时间复杂度为O(n³).

总结：循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。

1.6 指数阶

int n;
scanf("%d",&n);
int count = 0;
for(int i=0;i<pow(2,n);++i){
    printf("%d\n",++count);
}

• 循环语句要执行pow(2,n)次，所以时间复杂度为O(2ⁿ)

1.7 阶乘

long long factorial(int n){
    int res = 1;
    for(int i=1;i<n;++i){
        res*=i;
    }
    return res;
}

int n;
scanf("%d",&n);
int count = 0;
for(int i=0;i<factorial(n);++i){
    printf("%d\n",++count);
}

• 循环语句需要执行n!次，所以时间复杂度为O(n!)

• 练习

int n;
scanf("%d",&n);
int count = 0;
for(int i=0;i<n;++i){
    for(int j=0;j<i;++j){
        printf("%d\n",++count);
    }
}

• 第一层循环结构需要执行内部循环n次，内部循环的分别执行1，2，...，n-1次，等差序列求和(1+(n-1))*n/2，n^2/2+n/2，没有加法，不考虑常数，保留最高阶n^2/2，去掉最高阶前的系数，得到时间复杂度为O(n²)

• 常见的时间复杂度所耗时间的大小排序
  O(1)<O(logn)<O(n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

2.空间复杂度

• 运行完一个程序所需内存的大小
• 程序执行时所需存储空间
  1.固定部分：指令空间、数据空间等。
  2.可变部分：动态分配内存、递归栈等。