Python 数据结构与算法 —— 初识算法

红太狼 2022-02-13 13:13 228阅读 0赞

#### 算法是什么？ ####

> 举个简单例子：

> **我们要做一份蛋炒饭：**

> 1.  拿钱包，出门，去菜市场购买鸡蛋和大米以及油和盐——购买蛋炒饭的材料
> 2.  回家将大米淘洗干净放进电饭煲——煮熟大米
> 3.  将锅放在电磁炉上加热——往锅里倒适量油
> 4.  将鸡蛋打开放入油锅——翻炒鸡蛋至七分熟
> 5.  将适量煮熟的米饭倒入锅中，加盐——翻炒两分钟

> 以上就是制作一份简单蛋炒饭的步骤

> 如果把这些交给机器来做，也是如此，并且步骤将更加细分和严谨

> 简单来讲，这就是**算法**

**那么算法到底是什么呢？**

> 先来看一道简单的高中数学题：

> **现有a,b,c三个自然数，要求满足以下条件：**

> 1.a+b+c = 1000

> 2.a^2 + b^2 = c^2 (^代表平方)

> ***分析：***

> 首先排除数学公式，我们使用机器思维来计算这道题，能想到的办法也很简单，即一个一个数尝试  
> ，直到试出准确答案为止，此种方法我们称之为 **枚举法**

##### 上面数学题使用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("time:%d" % (end_time - start_time))
    print("finished!")

> **代码执行结果：**

C:\python3\setup\python.exe C:/Users/limia/Desktop/DataS/01_枚举组合.py
    a, b, c: 0, 500,500
    a, b, c: 200, 375,425
    a, b, c: 375, 200,425
    a, b, c: 500, 0,500
    time:121
    finished!
    
    Process finished with exit code 0

> ***注释：*** 在上面的代码中：计算这道数学题的同时，还引入了time模块来计算这段代码的运行时间，以方便之后对比算法效率

> 通过分析这道题，我们可以得知，a+b+c=1000，在有了a和b的值之后，c的值自然就可以计算为：1000-a-b，分析至此，则代码可以改进为以下：

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("time:%d" % (end_time - start_time))
    print("finished!")

> **代码执行结果：**

C:\python3\setup\python.exe C:/Users/limia/Desktop/DataS/01_枚举组合.py
    a, b, c: 0, 500,500
    a, b, c: 200, 375,425
    a, b, c: 375, 200,425
    a, b, c: 500, 0,500
    time:1
    finished!
    
    Process finished with exit code 0

> 通过对比，可以一目了然的发现，改进后的代码执行效率（1s）明显高于第一种代码执行效率（121s）

#### 算法的概念： ####

> 算法是计算机处理信息的本质

> 算法是独立存在的一种解决问题的方法和思想

> 计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务

#### 单纯以时间衡量算法效率是否是科学的、客观的？ ####

> ***答案：不客观***

> 假设在一台古老的计算机上运行上面的两个程序，则其所消耗的时间都将是极长的，因此单纯以时间计算算法的效率是不科学的。

> 在衡量算法的效率时，应当**脱离计算机**来估算

> 因此引入**时间复杂度**来衡量算法的效率

> **每台计算机执行的总时间不同，但是执行基本运算数量大体相同**

##### 上面的两个程序，以时间复杂度来表示算法效率： #####