算法图解

深藏阁楼爱情的钟 2022-10-22 09:26 141阅读 0赞

**1. 大O表示法表示的是算法的运行时间、占用空间以不同的速度增加。**

**2. 计算机内存就如同电影院寄存柜中很多抽屉的集合，每个抽屉都是有地址的。**

**3. 有3个小伙伴一起去看电影，但是只有2个座位相邻**

*  若使用数组的思想，这些人需要重新再去找3个相连的座位。一个解决方法是：找到预留大于3(暂时忽略等于3的情况)个相邻的座位，然后坐进去。但这样会造成内存的浪费。
 *  若使用链表，仅仅只需要将下一个座位(内存)的地址放到前一个座位中就行了，这样，他们只需要再找一个单独的位置就可以了。

**4. 散列表**

*  散列表如字典一样，可以通过给定键来查找值。如查找商品的价格，用散列表的时间复杂度为O(1)，用简单查找则需要O(n)的时间。

book = {
        "apple": 0.67, "milk":1.49}
    print(book["milk"])

*  防止重复。如在投票时每人只能投一张票，为了防止重复，可以首先创建一个散列表，当有人来投票时，可以查看他是否在散列表中。

voted = {
        }
    def check_voter(name):
        if voted.get(name):
            print("kick them out！")
        else:
            voted[name] = True
            print("let them vote!")
    
    check_voter("Tom")
    check_voter("Tom")

*  用作缓冲。如果两个键映射到同一个位置，就在这个位置存储一个链表。

**5. 广度优先搜索**

广度优先搜索可以回答两类问题：

*  第一类问题：从节点A出发，有前往节点B的路径吗？
 *  第二类问题：从节点A出发，前往节点B的哪条路径最短？

以人际关系网为例，找出朋友圈中的销售商（注意：朋友的朋友也是关系网中的一部分，不过属于第二层）：

from collections import deque
    
    graph = {
        }    # 假设的人际关系网
    graph["you"] = ["alice", "bob", "candy"]
    graph["bob"] = ["peggy"]
    graph["candy"] = ["bob", "tonny"]
    graph["alice"] = []
    graph["peggy"] = []
    graph["tonny"] = []
    
    def search(name):
        search_queue = deque()
        search_queue += graph[name]     # graph["you"]是一个数组，其中包含你的所有邻居["alice","bob","claire"]
        searched = []                   # 防止陷入死循环
        while search_queue:             # 只要不为空
            person = search_queue.popleft()
            if person_is_seller(person):
                print(person + "is a seller!")
                return True
            else:
                search_queue += graph[person]  # 该person不是销售商，将这个人的朋友都加入搜索队列中
                searched.append(person)
        return False
    
    def person_is_seller(name):   # 给定一种搜索规则，当名字的最后一个字母是'm',则这个人是seller
        return name[-1] == 'm'
    
    print(search("you"))