数据结构——第一章 算法

我们不关心编写程序所用的程序设计语言是什么，也不关心这些程序将跑在什么样的计算机中，我们只关心它所实现的算法。这样，不计那些循环索引的递增和循环终止条件、变量声明、打印结果等操作，最终，在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。——大话数据结构

场景：金融港到关谷广场有很多条路。如果选择路程近的，那么可能会堵车耗时（时间复杂度的性能变差）；如果选择耗时短的，那么可能会绕路（空间复杂度的性能变差）。到底选择走哪一条路，需要根据实际情况来综合考虑了。  编程算法中亦是如此，时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；相反的当追求一个较好的空间复杂度时，就可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。

• 算法的定义:算法是解决特定问题求解步骤的描述，在计算机中为指令的有限序列，并且每条指令表示一个或多个操作。
• 算法的特性:有穷性、确定性、可行性、输入、输出。
• 算法的设计的要求:正确性、可读性、健壮性、高效率和低存储量需求。
• 算法的度量方法:事后统计方法（不科学、不准确)、事前分析估算方法。

 测定运行时间最可靠的方法：计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比。 

两种求和方法：f(n)=n,f(n)=1

f(n)=n^2

 

算法时间复杂度

将算法中基本操作的执行次数作为算法时间复杂度的度量。时间复杂度不是执行完一段程序的总时间，而是其中基本操作的总次数。
在算法题中你总能找到一个n，可以称为问题的规模，如要处理的数组元素的个数为n，而基本操作所执行的次数是n的一个函数f(n)（这里的函数是数学中函数的概念，不是C或C++语言中函数的概念)。对于求其基本操作执行的次数，就是求函数f(n)。求出以后就可以取出 fn)中随n增大而增长最快的项，然后将其系数变为1，作为时间复杂度的度量，记为T(m)=O(f(m)中增长最快的项/此项的系数)。例如，f(n)=2n^3+4n^2+100，则其时间复杂度为T(n)=O(2n^3/2)=O(n^3)。实际上计算算法的时间复杂度就是给出相应的数量级，当f(n)与n无关时,时间复杂度T(n)=O(1);当f(n)与n是线性关系时， T(n)=O(n);当f(n)与n是二次方关系时，T(n)=O(n^2);以此类推。——天勤数据结构

用大写O()来体现算法时间复杂度的记法，推导大O阶方法:
1.用常数1取代运行时间中的所有加法常数。

2.在修改后的运行次数函数中,只保留最高阶项。

3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。

得到的结果就是大O阶。

比较各种时间复杂度的大小，常用的时间复杂度比较关系为

 （最重要的是增长率，随着n的增大，T(n)增长最慢的算法为最优算法） 

计算一个算法时间复杂度的具体步骤如下:
1)确定算法中的基本操作以及问题的规模,
2)根据基本操作执行情况计算出规模n的函数f(n)，并确定时间复杂度为T(n)=O(f(n)中增长最快的项/此项的系数)。
注意:一些排序算法，同样有n个待处理数据，但数据初始有序性不同，则基本操作的执行次数也不同。一般依照使得基本操作执行次数最多的输入来计算时间复杂度,即将最坏的情况作为算法时间复杂度的度量。

平均时间复杂度就是：加权平均时间复杂度（期望时间复杂度）。平均运行时间也就是从概率的角度看，这个数字在每一个位置的可能性是相同的，所以平均的查找时间为n/2次后发现这个目标元素。

要查找的元素 element 在数组中的位置，有 n+1 种情况：在数组的[0，n-1]索引位置中和不在数组中。 假设元素 element 在数组中与不在数组中的概率各为 1/2， 并且假设出现在索引[0, n-1]这 n 个位置的概率都是 1/n。根据概率乘法法则，要查找的元素 element出现在[0, n-1]中任意位置的概率就是 1/2n。到这里，就可以得到这样的计算公式： 1(1/2n) + 2(1/2n) +3(1/2n) + …… + n(1/2n) + n*(1/2) = (3n + 1)/4。得到的这个值就是概率论中的加权平均值，也叫做期望值。根据这个加权平均值，去掉常数项、低次幂项和最高次幂项的系数，我们得到的平均时间复杂度也是 O(n)。

常数阶 O(1)：无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是 O(1)。

对数阶O(log2n)：在循环中，每趟循环执行完毕后，循环变量都放大两倍。如果每趟循环执行完毕后，循环变量都放大 3 倍，那么该代码的时间复杂度为：O(log3n)

线性阶O(n)：for 循环会执行 n 趟，用 O(n)来表示它的时间复杂度。

线性对数阶 O(nlog2n) ：将O(log2n)的代码循环 n 遍的话，那就是 n*O(log2n)，也就是 O(nlog2n) 。

平方阶 O(n^2)：外层 i 的循环执行一次，内层 j 的循环就要执行 n 次。因为外层执行 n 次，那么总的就需要执行 n*n 次，也就是需要执行 n^2 次，时间复杂度为：O（n^2）。立方阶 O(n^3)，参考上面的 O(n^2)去理解，也就是需要用到 3 层循环。

 

指数阶 O(2^n)：当 n 为 10 的时候，需要执行 2^10 次。

阶乘阶 O(n!)：当 n 为 10 的时候，需要执行 10×9×8...2×1 次。

 

 练习——王道数据结构

1．循环主体中的变量参与循环条件的判断

找出主体语句中与Tn)成正比的循环变量，将之代入条件中进行计算。

int y=5;
while((y+1)*(y+1)
    y=y+1;

y加1的次数恰好与T(n)成正比，记t为该程序的执行次数并令t=y-5，有y=t+5,(t+5+1)×(t+5+1)

2．循环主体中的变量与循环条件无关
可采用数学归纳法或直接累计循环次数。多层循环时从内到外分析，忽略单步语句、条件判断语句，只关注主体语句的执行次数。此类问题又可分为递归程序和非递归程序:
递归程序一般使用公式进行递推。例如2.1的时间复杂度分析如下:
T(n)= 1+ T(n-1)= 1+1＋T(n- 2)= …=n-1+T(1)
即T(n)= O(n)。

2.1 求整数n (n≥0)的阶乘的算法如下，其时间复杂度是O(n)。

int fact(int n){
    if(n<=1) return 1;
    return n*fact(n-1);
}

求阶乘n!的递归代码，即nx(n-1)x…x1。每次递归调用时fact ()的参数减1，递归出口为fact(1)，一共执行n次递归调用fact ( )，故T(n)= O(n)。

 非递归程序可以直接累计次数，例如2.2和2.3。

2.2下面函数的时间复杂度是

int func(int n){
    int i=0, sum=0;
    while(sum
    return i;
}

 基本运算sum+=++i,它等价于++i ; sum=sum+i,每执行一次i自增1。i=1时,sum=0+1;i=2时, sum=0+1+2;i=3时, sum=0+1+2+3,以此类推得出sum=0+1+2+3+…+i=(1+i)*i/2，可知循环次数t满足( 1+t)*t/2 

 2.2 下面函数的时间复杂度是

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

 基本运算为i++，设执行次数为t,有txtxt≤n，即r^3≤n。故有

  2.3 其中n为正整数，则最后一行语句的频度在最坏情况下是O(n^2)

for(i=n-1;i>1;i--)
    for(j=1;j
        if(A[j]>A[j+1])
            A[j]与A[j+1]对换;

 这是冒泡排序的算法代码，最坏情况下的元素交换次数，当所有相邻元素都为逆序时，则最后一行的语句每次都会执行。此时，

 

3.一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别（或阶)。

 

 

上式中，n是问题的规模,为简单起见，设n是2的整数次幂。

算法的空间复杂度

场景：

我们在写代码时，完全可以用空间来换取时间，比如说，要判断某某年是不是闰年，你可能会花一点心思写了一个算法，而且由于是一个算法，也就意味着，每次给一个年份，都是要通过计算得到是否是闰年的结果。还有另一个办法就是，事先建立一个有2050个元素的数组（年数略比现实多一点)，然后把所有的年份按下标的数字对应，如果是闰年，此数组项的值就是1，如果不是值为0。这样，所谓的判断某一年是否是闰年，就变成了查找这个数组的某一项的值是多少的问题。此时，我们的运算是最小化了，但是硬盘上或者内存中需要存储这2050个0和1。
 

 算法在运行过程中所需的存储空间包括：

（1）输入输出数据占用的空间；

（2）算法本身占用的空间；

（3）执行算法所需的辅助空间。

其中输入和输出数据占用的空间取决于问题，与算法无关；算法本身占用的空间虽然与算法相关，但是一般其大小是固定的。

所以，算法的空间复杂度是指算法在执行过程中需要的辅助空间，也就是除算法本身和输入输出数据占用的空间外，算法临时开辟的存储空间。

如果算法所需的辅助存储空间的数量是问题规模 n 的函数，通常计作：S(n)=O(f(n))。其中，n为问题的规模，分析方法与算法的时间复杂度类似。

在做算法分析时，因为时间复杂度要比空间复杂度更容易出问题，所以一般情况下我们更多对时间复杂度进行研究。 从用户使用体验上看，更看重的程序执行的速度。一些缓存产品（redis）和算法（基数排序）本质就是使用空间来换时间。

 来源：《大话数据结构》，《王道数据结构》，《天勤数据结构》等