算法与数据结构的python概述

ゞ浴缸里的玫瑰 2023-06-24 10:25 50阅读 0赞

引子

**问题一：1+2+3+4+5+…+10000=？**

第一种解法：  
1+2=3,3+3=6，6+4=10,10+5=15…  
这是要算到猴年马月的节奏呀 果断弃之

第二种解法：  
聪明的高斯，这样玩：  
 （ 1 + 10000 ） × 10000 ÷ 2 = 50005000 （1+10000）\\times10000\\div2=50005000 （1\+10000）×10000÷2=50005000

在这一问题的解答上，高斯的方法真香！  
![在这里插入图片描述][20191222193439165.png]  
**问题二：冬天里，你和小红玩猜数字，小红随便想一个1～100的数字。你的目标是以最少的次数猜到这个数字。你每次猜测后，小红会说小了、大了或对了。在10次内猜对了，小红就答应今晚用你暖床。是不是听着很刺激**

第一种解法：  
你从1开始依次往上猜，猜测过程会是这样,小红皱着眉不断说小了  
![在这里插入图片描述][20191222200110987.png]  
![在这里插入图片描述][20191222200028899.png]  
这是简单查找，更准确的说法是傻找 。每次猜测都只能排除一个数字。如果小红想的数字是99，你得猜99次才能猜到！，注定今晚你和小红无缘了

第二种解法：  
你从50开始，小红笑着说小了，你接着说75…  
![在这里插入图片描述][20191222200533331.png]  
![在这里插入图片描述][20191222200606272.png]  
你每次猜测的是中间的数字，从而每次都将余下的数字排除一半。接下来，你猜63（50和75中间的数字）…这就是二分查找，每次猜测排除的数字个数如  
下:  
![在这里插入图片描述][2019122220111661.png]  
不管小红心里想的是哪个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字！恭喜你，小红今晚是你的人了。

**解析：对于包含n 个元素的有序列表，用二分查找最多需要 l o g 2 n log\_2 n log2n步1，而简单查找最多需要n 步。**

**二分查找的python实现**

def binary_search(list1, item):
        low = 0   # low和high用于跟踪要在其中查找的列表部分
        high = len(list1) - 1
        while low <= high:
            mid = (low + high) // 2
            guess = list1[mid]
            if guess == item:   # 猜对了
                return mid  # 返回位置
            elif guess > item:  # 猜大了
                high = mid - 1
            else:            # 猜小了
                low = mid + 1
    
        return None  # 没有找到
    
    my_list = [i for i in range(1,100)]  # 列表推导式生成0-100个数
    
    print(binary_search(my_list, 3))  # 别忘了索引从0开始

回到前面的二分查找。使用它可节省多少时间呢？简单查找逐个地检查数字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最多需要猜40亿次。换言之，最多**需要猜测的次数与列表长度相同，这被称为线性时间**（linear time）。  
二分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多需猜32次。厉害吧？**二分查找的运行时间为对数时间** （或 l o g log log时间）。

--------------------

算法 在计算机领域，我们同样会遇到各种高效和拙劣的算法。衡量算法好坏的重要标准有两个。通常指最糟的情形下的：

*  [时间复杂度][Link 1]（[采用大O表示法][O]）
 *  [空间复杂度][Link 2]（[采用大O表示法][O]）

理解：小明和小刚都是初入IT的新人，一天老板给他们布置了同一个需求让他们用代码实现出来，小明的代码运行一次要花100ms，占用内存5MB。小刚的代码运行一次要花100s，占用内存500MB。于是……小刚第二天就从公司消失了  
![在这里插入图片描述][20191222224823322.png]  
你经常会遇到的5种大O运行时间：

*  O ( l o g n log n logn)，也叫对数时间，这样的算法包括二分查找
 *  O (n)，也叫线性时间，这样的算法包括简单查找
 *  O ( n ∗ l o g n n \* log n n∗logn)，这样的算法包括快速排序——一种速度较快的排序算法。
 *  O ( n 2 n ^2 n2)，这样的算法包括选择排序——一种速度较慢的排序算法。
 *  O ( n ! n ! n!)，这样的算法包括[旅行商问题][Link 3]的解决方案——一种非常慢的算法.

假设你要绘制一个包含16格的网格，且有5种不同的算法可供选择：  
![在这里插入图片描述][20191222221153362.png]  
![在这里插入图片描述][20191222222006539.png]

时间复杂度的概念明白了，那空间复杂度呢：

--------------------

**问题三：给出下图所示的n个整数，其中有两个整数是重复的，要求找出这两个重复的整数。**  
![在这里插入图片描述][20191223142032239.png]  
第一种解法：  
你采用双重循环，遍历整个数列，每遍历到一个新的整数就开始回顾之前遍历过的所有整数，看看这些整数里有没有与之数值相同的，第1步，遍历整数3，前面没有数字，所以无须回顾比较。第2步，遍历整数1，回顾前面的数字3，没有发现重复数字。后续步骤类似，一直遍历到最后的整数2，发现和前面的整数2重复。  
![在这里插入图片描述][20191223142604135.png]  
这个算法的时间复杂度是 O ( n 2 ) O(n^2) O(n2)

第二种解法：  
当你遍历整个数列时，每遍历一个整数，就把该整数存储起来，就像放到字典中  
一样。当遍历下一个整数时，不必再慢慢向前回溯比较，而直接去“字典”中查找，看看有没有对应的整数即可。“字典”左侧的Key代表整数的值，“字典”右侧的Value代表该整数出现的次数（也可以只记录Key）。当遍历到最后一个整数2时，从“字典”中可以轻松找到2曾经出现过，问题也就迎刃而解了。  
![在这里插入图片描述][20191223142922693.png]  
读写“字典”本身的时间复杂度是 O ( 1 ) O(1) O(1)，所以整个算法的时间复杂度是 O ( n ) O(n) O(n)

第二种解法采用的这个所谓的“字典”，是一种特殊的数据结构，叫作散列表。这个数据结构需要开辟一定的内存空间来存储有用的数据信息。

**计算机的内存空间是有限的**，在时间复杂度相同的情况下，算法占用的内存空间自然是越小越好。**如何描述一个算法占用的内存空间的大小呢？这就用到了算法的另一个重要指标——空间复杂度**（space complexity）。

*  常量空间，当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作 O ( 1 ) O(1) O(1)
 *  线性空间，当算法分配的空间是一个线性的集合（如数组），并且集合大小和输入规模n成正比时，空间复杂度记作 O ( n ) O(n) O(n)
 *  二维空间，当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n成正比时，空间复杂度记作 O ( n 2 ) O(n^2) O(n2)
 *  递归空间，递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合，但是计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是 O ( n ) O(n) O(n)。

时间与空间的取舍:  
人们之所以花大力气去评估算法的时间复杂度和空间复杂度，其根本原因是计算机的运算速度和空间资源是有限的。虽然目前计算机的CPU处理速度不断飙升，内存和硬盘空间也越来越大，但是面对庞大而复杂的数据和业务，我们仍然要精打细算，选择最有效的利用方式。

在寻找重复整数的问题三中，双重循环的时间复杂度是 O ( n 2 ) O(n^2) O(n2)，空间复杂度是 O ( 1 ) O(1) O(1)，这属于牺牲时间来换取空间的情况。相反，字典法的空间复杂度是 O ( n ) O(n) O(n)，时间复杂度是 O ( n ) O(n) O(n)，这属于牺牲空间来换取时间的情况。在绝大多数时候，时间复杂度更为重要一些，我们宁可多分配一些内存空间，也要提升程序的执行速度。

--------------------

数据结构 算法的概念理解清楚了，下面就是数据结构。如果把算法比喻成美丽灵动的舞者，那么数据结构就是舞者脚下广阔而坚实的舞台。数据结构，对应的英文单词是data structure，是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。

常见的数据结构：

*  线性结构，线性结构是最简单的数据结构，包括数组、链表，以及由它们衍生出来的栈、队列、哈希表。  
    ![在这里插入图片描述][20191223150719128.png]
 *  树是相对复杂的数据结构，其中比较有代表性的是二叉树，由它又衍生出了二叉堆之类的数据结构。  
    ![在这里插入图片描述][20191223151016754.png]
 *  图是更为复杂的数据结构，因为在图中会呈现出多对多的关联关系。  
    ![!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/20191222223617378.png][https_img-blog.csdnimg.cn_20191222223617378.png]
 *  除上述所列的几种基本数据结构以外，还有一些其他的千奇百怪的数据结构。它们由基本数据结构变形而来，用于解决某些特定问题，如跳表、哈希链表、位图等。

下一节我们将进入数据结构的世界，并从中认识许多有趣的算法。

--------------------

1.  我会经常会谈到log，因此你必须明白对数的概念 ↩︎

[20191222193439165.png]: https://img-blog.csdnimg.cn/20191222193439165.png
[20191222200110987.png]: https://img-blog.csdnimg.cn/20191222200110987.png
[20191222200028899.png]: https://img-blog.csdnimg.cn/20191222200028899.png
[20191222200533331.png]: https://img-blog.csdnimg.cn/20191222200533331.png
[20191222200606272.png]: https://img-blog.csdnimg.cn/20191222200606272.png
[2019122220111661.png]: https://img-blog.csdnimg.cn/2019122220111661.png
[Link 1]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E6%80%A7/5930669?fr=aladdin
[O]: https://www.zhihu.com/question/21387264/answer/830343420
[Link 2]: https://baike.baidu.com/item/%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/9664257?fr=aladdin
[20191222224823322.png]: https://img-blog.csdnimg.cn/20191222224823322.png
[Link 3]: https://baike.baidu.com/item/%E6%97%85%E8%A1%8C%E5%95%86%E9%97%AE%E9%A2%98/7737042?fr=aladdin
[20191222221153362.png]: https://img-blog.csdnimg.cn/20191222221153362.png
[20191222222006539.png]: https://img-blog.csdnimg.cn/20191222222006539.png
[20191223142032239.png]: https://img-blog.csdnimg.cn/20191223142032239.png
[20191223142604135.png]: https://img-blog.csdnimg.cn/20191223142604135.png
[20191223142922693.png]: https://img-blog.csdnimg.cn/20191223142922693.png
[20191223150719128.png]: https://img-blog.csdnimg.cn/20191223150719128.png
[20191223151016754.png]: https://img-blog.csdnimg.cn/20191223151016754.png
[https_img-blog.csdnimg.cn_20191222223617378.png]: https://img-blog.csdnimg.cn/20191223151042379.png