《算法图解》读书笔记-2 第一章 算法简介 二分查找算法(python实现代码)时间复杂度 旅行商问题

发布时间:2023-09-27 08:30

文章目录

  • 1.本章内容
  • 2.章节引言
    • 2.1 本书主要内容
    • 2.2 问题解决技巧
  • 3.二分查找
    • 3.1 什么是二分查找?
    • 3.2 二分查找的工作原理
    • 3.3 代码实现二分查找算法
    • 3.3\' 示例代码
    • 3.4 二分查找的时间复杂度
  • 4.大O表示法
    • 4.1 大O表示法基本概念
    • 4.2 常见的大O运行时间
  • 5.旅行商问题
  • 6.本章小结

1.本章内容

  • 为阅读后续内容打下基础
  • 编写第一种查找算法——二分查找
  • 学习如何谈论算法的运行时间——大O表示法
  • 了解一种常用的算法设计方法——递归
    章节目录如下:
    \"《算法图解》读书笔记-2

2.章节引言

2.1 本书主要内容

什么是算法?
算法是一组完成任务的指令。
速度快/可以解决有趣的问题的算法是我们本书研究的重点:

  • 讨论二分查找&演示算法如何提高代码的速度。——第一章
  • GPS设备使用图算法来计算前往目的地的最短路径——第六七八章
  • 可以使用动态规划来编写下国际跳棋的AI算法——第九章
    介绍算法的方法:举例&提供实例 再使用大O表示法讨论其运行时间 最后探索它可以解决的其他问题。
    另外 本书将帮助我们

学习比较不同算法的优缺点——体会到改用不同的数据结构就可以让结果大不相同

2.2 问题解决技巧

本书将带我们学习一些问题解决技巧

  • 喜欢开发电子游戏? ——使用图算法编写跟踪用户的AI系统
  • 对推荐算法感兴趣? ——使用K最近邻算法编写推荐系统
  • 发现有些问题在有限时间是不可解的? ——学习NP完全问题 来识别这样的问题并且设计找到近似答案的算法
    总而言之——

读完本书 你将 熟悉一些使用最为广泛的算法。利用这些新学到的知识,你可以学习更具体的AI算法、数据库算法。

3.二分查找

3.1 什么是二分查找?

\"《算法图解》读书笔记-2
二分查找是一种算法,其输入是一个有序的元素列表
如果要查找的元素包含在列表中,二分查找返回其位置,否则返回null
\"《算法图解》读书笔记-2

3.2 二分查找的工作原理

随便想一个1-100的数字
\"在这里插入图片描述\"
目的:最少的次数猜到这个数字。
怎么做到呢?
是这种方法么?
\"《算法图解》读书笔记-2
nonono
这种方法才对哦
\"《算法图解》读书笔记-2
\"《算法图解》读书笔记-2
不管要猜1-100之间的哪个数字 在7次之内都能通过二分法猜到~
结论:

对于包含n个元素的列表 用二分查找最多需要\"在这里插入图片描述\"

3.3 代码实现二分查找算法

函数binary_search接受一个有序数组要搜索的元素。如果此元素包含在数组中,这个函数将返回其位置。
具体逻辑如下:
\"《算法图解》读书笔记-2

def binary_search(list, item):
    low = 0
    high = len(list) - 1
    #low 和 high 用来跟踪要在其中查找的列表部分

    while low <= high: #范围缩小到只剩一个元素为止(如果再找不到那只能return None咯~)
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid # 找到这个元素啦~
        if guess > item:
            high = mid - 1 #list[mid]太大了! 上限是比list[mid]小一丢丢的那个数
        if guess < item:
            low = mid + 1 #list[mid]太小了! 下限是比list[mid]大一丢丢的那个数
    return None#没有找到指定元素
if __name__ == \"__main__\":
    #测试用的主函数~
    my_list = [1, 3, 5, 7, 9]
    print(binary_search(my_list, 7))
    print(binary_search(my_list,-1))

测试得到结果\"在这里插入图片描述\"

3.3’ 示例代码

这里是 《图解算法》给出的标准答案
给出两种二分法的算法~
更多原书给出的代码戳这个链接下载 ~
多跑一跑嘿嘿嘿

class BinarySearch():

  def search_iterative(self, list, item):
    # low and high keep track of which part of the list you\'ll search in.
    low = 0
    high = len(list) - 1

    # While you haven\'t narrowed it down to one element ...
    while low <= high:
      # ... check the middle element
      mid = (low + high) // 2
      guess = list[mid]
      # Found the item.
      if guess == item:
        return mid
      # The guess was too high.
      if guess > item:
        high = mid - 1
      # The guess was too low.
      else:
        low = mid + 1

    # Item doesn\'t exist
    return None

  def search_recursive(self, list, low, high, item):
    # Check base case 
    if high >= low: 
  
        mid = (high + low) // 2
        guess = list[mid]
  
        # If element is present at the middle itself 
        if guess == item:
            return mid 
  
        # If element is smaller than mid, then it can only 
        # be present in left subarray 
        elif guess > item: 
            return self.search_recursive(list, low, mid - 1, item) 
  
        # Else the element can only be present in right subarray 
        else: 
            return self.search_recursive(list, mid + 1, high, item) 
  
    else: 
        # Element is not present in the array 
        return None

if __name__ == \"__main__\":
  # We must initialize the class to use the methods of this class
  bs = BinarySearch()
  my_list = [1, 3, 5, 7, 9]
  
  print(bs.search_iterative(my_list, 7)) # => 1

  # \'None\' means nil in Python. We use to indicate that the item wasn\'t found.
  print(bs.search_iterative(my_list, -1)) # => None

3.4 二分查找的时间复杂度

对数时间~
\"《算法图解》读书笔记-2

4.大O表示法

4.1 大O表示法基本概念

  • 指出了算法的速度有多快。
  • 大O表示法 让你能够比较操作数,它指出了算法运行时间的增速 指出了算法需要执行的操作数
  • 大O表示法指出了最糟情况下的运行时间

4.2 常见的大O运行时间

\"《算法图解》读书笔记-2
我们来画个图 举个栗子感受一下
\"《算法图解》读书笔记-2
ps:最后那个算法是什么鬼哦
下面我们就来看看这个时间复杂度为\"《算法图解》读书笔记-2的算法~

5.旅行商问题

旅行商问题是一个运行时间极长的算法。这个算法要解决的是计算机科学领域非常著名的旅行商问题,其计算时间增加得非常快,而有些非常聪明的人都认为没有改进空间。

\"《算法图解》读书笔记-2

可以看到 如果城市数稍微增多 操作数就会变得超级多
\"《算法图解》读书笔记-2

6.本章小结

入门算法的一个基础小章节 呼~来总结一下

  • 二分查找的速度
    比简单查找要快得多哦~
    二分查找的代码见3.3
    \"《算法图解》读书笔记-2
  • 算法运行时间用大O表示法表示

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号