数据结构和算法-1-算法的引入和算法时间复杂度

水深无声 2022-01-23 09:01 157阅读 0赞

最近有时间来系统学习下常见数据结构和算法的知识，所以，还是通过纪录笔记放在博客的方式来督促自己学习。算法对于很多程序员都接触不到的，何况是一个测试人员。但是面试过程中，多多少少都有算法题的面试。所以，学习算法，短期来看是为了跳槽准备，长期来看，是锻炼一个人解决问题的思路的提升的一个途径。

**1.算法的引入**

来看一个问题：如果 a+b+c = 1000, 且 a^2 + b^2 = c^2（勾股定理），如何求出所有a b c的组合。

问题分析：

上面告诉两个条件，从数学角度来说，上面有3个未知数，只有两个表达式条件，我们第一反应是转换成二元二次方程来解答。这里我们是计算机通过代码来解决问题。字面意思就是 a的取值范围是0到1000， b的取值范围是0到1000， c的取值范围是0到1000, 然后加上题目的两个表达式条件，利用for嵌套循环，计算机肯定能帮我们找出a b c的取值。

代码实现：

根据上面的分析，python代码实现如下：

import time
    
    start_time = time.time()
    for a in range(0, 1001):
        for b in range(0, 1001):
            for c in range(0, 1001):
                if a + b + c == 1000 and a**2 + b**2 == c**2:
                    print("a, b, c: %d, %d, %d" % (a, b, c))
    end_time = time.time()
    print(end_time - start_time)

其实上面代码思路也是用到了一个方法，叫**枚举法**，就是一个一个列出来去尝试，不行，换下一个值继续去匹配。

运行之后得到结果：

a, b, c: 0, 500, 500
    a, b, c: 200, 375, 425
    a, b, c: 375, 200, 425
    a, b, c: 500, 0, 500
    176.38802433013916

也就是差不多花费三分钟（176秒多），找出了符合条件的a b c的四种取值组合。如果没有计算机，人也是可以根据这个思路，一步一步去算，只不过时间更是不知道有多慢。这个时间开销，我们很不满意，对用户来说，还是太慢了。有没有什么办法提升以下计算效率。

优化上面代码：

根据数学知识，我们用代码实现二元二次方程的思路，c = 1000 - a - b; 来减少第三层嵌套for循环。

import time
    
    start_time = time.time()
    for a in range(0, 1001):
         for b in range(0, 1001):
            c = 1000-a-b
            if a**2 + b**2 == c**2:
                print("a, b, c: %d, %d, %d" % (a, b, c))
    end_time = time.time()
    print(end_time - start_time)

运行结果输出：

a, b, c: 0, 500, 500
    a, b, c: 200, 375, 425
    a, b, c: 375, 200, 425
    a, b, c: 500, 0, 500
    1.5549931526184082

这么一看，发现时间缩短了不到2秒，这个计算效率大大提升。同样解决一个问题，由于我们第二种方法减少了一次for循环嵌套，导致计算效率提高了很多倍，这个就是算法的重要性。

**2.什么是算法**

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或者某个存储地址供以后再调用。**算法是独立存在的一种解决问题的方法和思想。**对于算法而言，实现的编程语言并不重要，重要的是思想。

**算法的五大特性**：  
1：输入：算法具有0个或多个输入  
2：输出：算法至少有一个或多个输出  
3：有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成  
4：确定性：算法内的每一步都有确定的含义，不会出现二义性。  
5：可行性：算法的每一步都是可行的，也就是说每一步都能执行有限的次数完成。

**3.时间复杂度和大O表示法**

上面我们通过两个方法来求出a b c的取值组合，第二个方法比第一个方法，从时间效果来看，快很多，所以我们很容易得出结论，第二个算法比第一个算法效率要高。那么算法是通过时间来衡量，确实最直观地，我们从时间上来看到算法和算法之间的效率不同。但是，单靠时间是不可靠的，例如，同一个算法，在一个I7的CPU上运行和拿到一个1995年之前的个人PC电脑上运行，这种时间来比较就有点不合适了。所以，我们一般从算法的执行计算数量这个维度去考察算法的效率。执行数量可以这么理解，上面3个for循环嵌套的代码，每一行代码都有确定的执行步骤数量，所有代码行的执行步骤数量相加，就得到了这个算法的执行步骤数量。因为每台机器要执行这么多步骤数量大体相同，所以这个执行步骤数量就拿来衡量算法的效率。

我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位，那么有多少个基本操作就代表会花费多少时间单位。对于不同机器而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作，在规模数量级上说却是相同的。由此可以忽略机器环境影响而客观的反应算法的时间效率。

对于算法的时间效率，我们可以用“**大O记法**”来表示。  
“大O记法”：对于单调的整数函数f，如果存在一个整数函数g和实常数c>0,使得对于充分大得n，总有  
f(n)<=c\*g(n),就说函数g是f得一个渐进函数（忽略常数），记作为f(n)=O(g(n)),也就是说在趋向无穷得  
极限意义下，函数f的增长速度收到函数g的约束，亦函数f与函数g的特征相似。

**时间复杂度**：假设存在函数g，使得算法A处理规模为n的问题实例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A  
的渐进时间复杂度，简称时间复杂度，记为T(n)

**4.如何理解“大O记法”**

我们通过“大O记法”的定义，我们来计算下上面 a b c这题的第一种代码实现方式的时间复杂度的计算过程。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70][]

我们根据上面这个图代码对应行来分析（第4到8行代码），先分析每行代码执行步骤数目。

分析过程：

第4行：a的取值范围是0到1000，所以这个for循环要执行1000次

第5行：b的取值范围是0到1000，所以这个for循环要执行1000次

第6行：c的取值范围是0到1000，所以这个for循环要执行1000次

第7行：如果不细分步骤，第7和第八两行当作2个步骤，如果细分，a + b + c是一个步骤， 判断a + b + c ==1000是一个步骤，a\*\*2是一个步骤，所以细分，第七行存在需要执行 8个步骤数目。

这样，我们把每一行代码需要执行步骤次数计算出来是

T = 1000 * 1000 * 1000 * 8
    简写成 T = 8*1000^3

如果，这里把1000改成n, 把这个问题规模扩大，这个算法的时间复杂度可以写成

T（n）= 8*n^3

我们在计算时间复杂度的时候，只关注大头部分，会去掉旁支末节部分，一般我们可以这样认为 n^3和1000\*n^3是等价，所以我们上面文章开头写的第一种枚举法的时间复杂度是 O(n^3)。

根据这个时间复杂度计算原则，我们计算第二种算法的时间复杂度为O(n^2)，这个比第一个效率要高，当然如果时间复杂度为n^1，那么这个算法效率就更高。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70]: /images/20220123/931bcba91fcc49af9fde76aadf67d555.png