408数据结构—时间复杂度的计算

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

时间复杂度在统考中是一大重点，在算法设计题里通常都会要求分析时间复杂度，空间复杂度，同时还会出现考察时间复杂度的选择题，所以需要考生熟练掌握

一、时间复杂度

频度: 一个语句的频度是指该语句在算法中被重复执行的次数

           算法中所有语句的频度之和记为T(n),是问题规模n的函数

时间复杂度主要分析T(n)的数量级，也就是所有语句执行的次数之和的数量级

也可以说是最深层循环中的语句（基本运算）的频度的数量级

表示: T（n）＝O(f(n))

这里补充一下算法设计与分析课程中有关大O表示法等渐进符号的定义

O: f(n)=O(g(n)）当且仅当存在正的常数C和n0，使得对于所有的n≥ n0，有f(n)≤Cg(n)。此时，称g(n）是f(n）当 n充分大时的一个上界。

Ω: f(n)=Ω(g(n)）当且仅当存在正的常数C和n0，使得对于所有的n≥n0，有f(n)≥Cg(n)。此时，称g(n）是f(n）当 n充分大时的一个下界。

Θ: f(n)=Θ(g(n)）当且仅当存在正的常数C1,C2和n0，使得对于所有的n≥n0，C1g(n)≤f(n)≤C2g(n)。此时，称f(n)与g(n）同阶。

算法的时间复杂度不仅依赖于问题的规模，还取决于待输入数据的性质

比如在数组中查找，要查找的元素在数组开头和在数组末尾肯定不一样

所以衍生出三种复杂度，即最好情况，最坏情况，平均情况的复杂度

其中平均情况就是指输入所有实例在等概率出现的情况下算法的期望运行时间。

我们一般只考虑最坏和平均时间复杂度

举个例子，比如刚才的查找，假设数组长度为n

那么最坏情况就是要查找的数正好在数组的最后，需要遍历一整个数组，复杂度为O（n）

计算平均时间复杂度时，每一个情况的概率就是1/n

设pi是查找第i个位置上元素的概率，则平均比较次数为1×1/n+2×1/n+…+n×1/n＝1/n ×n(n＋1)/2 = （n＋1）/2，其实复杂度还是O（n）

考虑两个规则，加法和乘法

加法规则:   T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

乘法规则：T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))= O(f(n)×g(n))

这里提到，加法只保留阶数最大的，关于阶数，我们有如下常识：

O(1) < O(log2(n))< O(n)< O(nlog2(n))< O(n²) < O(n³)<0(2") < O(n!) <O(n")

这里直接记闲鱼学长口诀：常对幂指阶

 二、空间复杂度

算法的空间复杂度S(n)为该算法所需的存储空间，即

S(n)＝O(g(n))

一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。例如，若算法中新建了几个与输入数据规模n相同的辅助数组，则空间复杂度为O(n)。

单独拿出空间复杂度为O（1）的情况：

表示算法原地工作，所需的辅助空间为常量，辅助空间大小与问题规模n无关，不是不需要辅助空间
 

void test(int n){
     int falg[n][n];
     int other[n];
     int i;
}

该算法的空间复杂度为O(n²)+O(n)+O(1)=O(n²)

三、有关时间复杂度的计算

总结技巧：找n和运行次数t的关系

void fun(int n){
     int i＝1;
     while(i＜=n)   i=i*2;
}

这里，i的变化为1,2,4,8,16…即2的t次方，t为次数

想一想运行多少次i的值才能等于n，跳出循环呢，也就是2的t次方＝n

n＝log2(n)，所以时间复杂度O（logn）,里面的2可以省略

void fun(int n){
     int i=0;
     while(i*i*i＜=n)   i++;
}

针对于这个，我们还是找关系

对于每个i，i的三次方分别会是0,1,8,27… 每次都是次数t³与n比较

于是乎，当t³＝n，循环跳出

所以时间复杂度为O(n的1/3次)

count=0;
for(k=1;k＜=n;k*=2){
   for(j=1;j＜=n;j++){
      count++;
 }
}

(2014统考)

这个题目我一开始也做错了，关键还是在于看语句执行了多少次

外层循环:k=1,2,4,8,…,n

内层循环:始终为n

那么就看k增长到n用了几次，也就是几个n

不难看出经过log2(n)次，一共是O(nlogn)

int sum=0;
for(int i=1;i＜n;i*=2)
    for(int j=0;j＜i;j++)
        sum++;

（2022统考）

还是老老实实分析执行次数

外层循环:1,2,4,8一直到n

内层循环：1,2,4,8一直到n

实际运算次数就是内层这些次数之和，即2的幂，等比数列之和

等比数列的项数其实是外层循环的个数

外层循环有几个呢？t＝log2（n）＋1，加1是因为多了第一项1，是2的0次方

内层等比数列求和:首项为1，公比为2，项数为t

S＝1+2+4+8+…=1×(1-2的t次)／(1-2)＝2的t次方-1

由于t前面计算得，是log的，于是整体S＝O(n)

int count=0;
for(int i=0;i*i＜n;i++)
    for(int j=0;j＜i;j++)
        count++;

(2025统考)

 外层循环:  0,1,4,9…n

内层循环：0,1,2,3…√n

于是乎内层直接相加就行，得到O(n)