【数据结构-1】例解算法复杂度

一、数据结构和算法的定义

1、数据结构

数据结构是计算机存储、组织数据的方式，指相互之间一种或多种特定关系的数据元素的集合。通俗地说，数据结构就是数据元素+数据元素之间的关系+在上面可以执行的操作。

2、算法

算法是解决一个问题的、明确有限步骤的指令序列，算法满足以下5个特性：
（1）有穷性：一定会在有限步之后结束。
（2）确定性：同样的输入，每一步执行结果唯一，不会这一次产生一个结果，下一次产生另一个结果。
（3）可行性：里面的每一条步骤都能实际执行出来。
（4）输入：接收0个或多个输入。
（5）输出：至少产生1个输出。

二、复杂度

1、如何衡量算法效率

首先什么是算法效率？算法效率是用来衡量一个算法好不好、快不快、费不费内存的指标。算法效率分成两部分，用时间效率用来衡量运行快慢，用空间效率用来衡量占用额外开辟的空间的多少。时间效率用时间复杂度来表示，空间效率用空间复杂度来表示。

2、复杂度的概念

算法在编写成可执行程序后，运行时需要耗费时间资源和空间（内存）资源，因此可以从时间和空间两个维度上衡量算法的好坏，即时间复杂度和空间复杂度。
复杂度是用来描述，当数据量变多的时候，算法的开销增长趋势；它不是精确的运行时间，不是精确字节数，只是增长趋势。

三、时间复杂度

程序的运行时间=单条二进制指令耗时 * 运行次数。单条二进制指令的耗时，是硬件、编译器、语言带来的，不属于算法本身的属性，时间复杂度研究的是算法本身，所以，时间复杂度主要通过统计算法中基本操作的执行次数，随输入规模n的增长趋势来衡量一个算法的运行快慢。
在计算机科学中，算法的时间复杂度是一个函数式T(N)，T（N）计算了程序的执行次数。执行次数就可以表示程序时间效率的优劣。

1、大O的渐进表示法

实际情况中，我们并不是用精确的指令执行次数来表示程序的好坏，这样比较麻烦，且太琐碎。而我们计算时间复杂度只要知道能代表执行次数的增长量级就可以了。所以，复杂度的表示通常使用大O的渐进表示法。
规则：
（1）在时间复杂度函数式T(N)中，只保留最高阶项，去除那些低阶项。
（2）如果最高阶项存在且系数不是1，则去除这个项目的常数系数。
（3）如果只有常数项，则用1取代所有加法常数。

2、示例

（1）

voidFunc1(intN){intcount=0;for(inti=0;i<N;i++){for(intj=0;j<N;j++){count++;}}for(intk=0;k<2*N;k++){count++;}intM=10;while(M--){count++;}}

Func1的基本操作次数T(N) = N²+2N+10，根据大O的渐进表示的推导规则，可知时间复杂度为O(N²)。
（2）

voidFunc2(intN){intcount=0;for(intk=0;k<2*N;++k){++count;}intM=10;while(M--){++count;}printf("%d\n",count);}

Func2的基本操作次数T(N) = 2N+10，根据大O的渐进表示的推导规则，可知时间复杂度O(N)。
（3）

voidFunc3(intN,intM){intcount=0;for(intk=0;k<M;k++){count++;}for(intk=0;k<N;k++){count++;}printf("%d\n",count);}

Func3的基本操作次数T(N,M) = M + N,时间复杂度 (大O表示法)只保留最高阶，为O(N +M）。
什么时候可以简化？如果题目约定N,M是同量级，一般就写O(N+M),当明确知道其中一个远小于另一个，比如M是固定常数时，才会写成O(N)。
（4）

voidFunc4(intN){intcount=0;for(intk=0;k<100;k++){count++;}printf("%d\n",count);}

Func2的基本操作次数T(N) = 100，根据大O的渐进表示的推导规则第三条，可知时间复杂度为O(1)。
（5）

constchar*strchr(constchar*str,intcharacter){constchar*p_begin=str;while(*p_begin!=character){if(*p_begin=='\0')returnNULL;p_begin++;}returnp_begin;}

先来计算strchr函数的基本操作次数T(N)，这里得分类讨论，因为根据待查找字符在字符串中的不同位置，查找可以分为最好情况、最坏情况和平均情况。
首先如果字符串中的首字符就是待查找字符，就属于最好情况，此时T(N) = 1;
如果待查找字符处在字符串中的最后一个位置，就属于最坏情况，此时T(N) = N;
如果待查找字符在字符串的中间位置，此时T(N) = N/2。
因此strchr函数的时间复杂度需要分为三种情况，分别为最好情况O(1)、最坏情况O(N)、平均情况O(N)。

通过案例5，可以得知，有些算法的时间复杂度是需要分情况讨论的。最好情况是任意输入规模的最小运行次数，属于下界；最坏情况是任意输入规模的最大运行次数，属于上界；另外，还有平均情况。但大O的渐进表示法在实际情况中关注最坏情况下的时间复杂度。
（6）一版冒泡排序的时间复杂度解析：

```cvoidBubbleSort(int*a,intn){assert(a);for(size_tend=n;end>0;--end){intexchange=0;for(size_ti=1;i<end;++i){if(a[i-1]>a[i]){Swap(&a[i-1],&a[i]);exchange=1;}}if(exchange==0)break;}}

首先还是来求解T(N)。
分类讨论，①最好情况：数组本来就有序，内层循环跑一遍，没有交换，exchange = 0,直接break。循环次数为n-1次，时间复杂度为O(n)。
②最坏情况：数组完全逆序，外层循环一共执行n次，内层循环的次数不是固定的，会随着end的递减而改变。所以总的执行次数需要累加每一次内层循环执行的次数。第一次外层循环end = n，内层循环执行n - 1次；第二次外层循环end = n - 1,内层循环执行n - 2次；第三次外层循环end = n - 2,内层循环执行n - 3次,…,第n次外层循环end = 1，内层循环执行0次。由于每一次外层循环，内层循环执行的次数之间构成了等差数列，而最后一次外层循环，内层循环为0不方便我们求解等差数列公式，所以假设最后一次执行1次。
所以，T(N) = (n-1) +(n-2) +(n-3) +…+1 = (n-1+1)*(n-1) / 2=½(n²)+½n。时间复杂度为O(N²)。
③平均情况：随机乱序数组，一般记作O(n²)。虽然部分轮次可以借助exchange标记提前终止，但整体比较次数依旧是n²量级，常数相比最坏情况小一些。
（7）

voidfunc5(intn){intcnt=1;while(cnt<n){cnt*=2;}}

可以看出cnt *= 2这句的执行次数是随着n的取值而不同的。所以，简单粗暴的求解方式就是代值计算，当n = 2时，cnt *= 2执行了1次；当n = 4时，cnt *= 2执行了2次；当n = 8时，cnt *= 2执行了3次。规律是：假设执行的次数为x,则2^x = n,即x = log₂n。所以时间复杂度为O(log₂n)。

注：当n接近无穷大时，底数的大小对结果影响不大。所以，一般情况下底数可以不写，直接写为logn。
（7）计算阶乘递归的时间复杂度

longlongFunc6(size_tN){if(0==N)return1;returnFunc6(N-1)*N;}

递归算法的时间复杂度 = 单次递归的时间复杂度 * 递归次数。在以上代码段中，可以看出，在Func6(N)中调用了Func6(N-1),接着Func6(N-1)中调用了Func6(N-2),…,最后调用Func6(0),所以递归调用了N次，时间复杂度为O(N)。

至此，关于时间复杂度及例解时间复杂度就结束了。

四、空间复杂度

空间复杂度是用来衡量一个算法的空间效率的指标，用一个算法在运行过程中需要额外临时开辟的空间大小来衡量。

1、示例

（1）先看冒泡排序这段代码

voidBubbleSort(int*a,intn){assert(a);for(size_tend=n;end>0;--end){intexchange=0;for(size_ti=1;i<end;++i){if(a[i-1]>a[i]){Swap(&a[i-1],&a[i]);exchange=1;}}if(exchange==0)break;}}

该冒泡排序中，额外申请的空间有exchange等有限个局部变量，使用了常数个额外空间，因此，空间复杂度为O(1)。

（2）

longlongFunc6(size_tN){if(0==N)return1;returnFunc6(N-1)*N;}

Func6递归调用了N次，额外开辟了N个函数栈帧，每个栈帧使用常数个空间，因此空间复杂度为O(N)。

至此，空间复杂度及例解空间复杂度也结束了。