《算法图解》第一章笔记与课后练习

软件环境:Python 3.7.0b4

一、二分查找

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

  # 只要范围没有缩小到只有一个元素,就继续循环
  while low <= high:
    # 检查中间的元素
    mid = (low + high) / 2
    guess = list[mid]
    # 如果猜的数是对了,返回结果
    if guess == item:
      return mid
    # 如果猜的数大了,上限减1
    if guess > item:
      high = mid - 1
    # 如果猜的数小了,下限加1
    else:
      low = mid + 1

  # 如果没有这个元素,返回None
  return None

my_list = [1, 3, 5, 7, 9] ##测试数据

二、一些常见的大O运行时间

下面按从快到慢的顺序列出经常遇到的5种大O运行时间:

  • O(log n):对数时间,这样的算法包括二分查找。
  • O(n):线性时间,这样的算法包括简单查找。
  • O(n * log n):这样的算法包括快速排序。
  • O(n2):这样的算法包括选择排序。
  • O(n!):这样的算法包括旅行商问题的解决方案。

三、课后练习

答案(有更好的欢迎在底下评论或私信)

1.1:128->64->32->16->8->4->2->1,所以最多需要7步。

1.2:翻倍后顶多会增加一步,所以是8步。

1.3:可以根据字母姓氏进行二分查找,所以是O(log n)。

1.4:属于简单查找,所以是O(n)。

1.5:属于简单查找,所以是O(n)。

1.6:O(n)。

四、小结

  • 二分查找的速度比简单查找要快许多,数据越大,差距就越明显。
  • O(log n)比O(n)快。需要搜索的元素越多,前者比后者就快得越多。
  • 算法运行时间并不以秒为单位。
  • 算法运行时间是从其增速的角度来度量的。
  • 算法运行时间用大O表示法表示。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

矩阵快速幂小结

      矩阵快速幂大概是用来解决这样一类问题,当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办? ...

33150
来自专栏owent

PKU POJ 1724 ROADS 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1724

7220
来自专栏新智元

【看图识算法】这是你见过最简单的 “算法说明书”

【新智元导读】像阅读宜家的安装说明书一样学习算法,是怎样的体验?不伦瑞克工业大学的三名研究者制作了这份“算法说明书”,简明传神地解释了一些基本算法,一起来看图说...

38280
来自专栏小樱的经验随笔

鸽巢原理(抽屉原理)的详解

抽屉原理 百科名片 ? 桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放两个苹果。这一现象就是我们所说的“抽屉原理”...

54570
来自专栏mathor

LeetCode69. x 的平方根

 这道题直接一个return Math.sqrt就出来了,但是秉承着学习的心态,尝试着用二分法ac  首先要确定的就是左右区间,左区间是0无疑了,那么右...

22020
来自专栏coolblog.xyz技术专栏

科普:String hashCode 方法为什么选择数字31作为乘子

某天,我在写代码的时候,无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现,发现并不是很复杂。但是我从源码中发现了一...

713190
来自专栏机器学习和数学

[数据结构和算法]《算法导论》动态规划笔记(1)

动态规划是求解最优化问题的方法,这类问题有很多可行解,每个解都有一个值,我们希望寻找具有最优值的解。我们称这个解为问题的一个最优解,而不是最优解,因为可能有多个...

407100
来自专栏小詹同学

Leetcode打卡 | No.011 盛最多水的容器

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

18520
来自专栏程序员叨叨叨

7.2 uniform

Cg 语言将输入数据流分为两类(参见文献[3]Program inputs and Outputs ):

8640
来自专栏java 成神之路

高亮标红

30680

扫码关注云+社区

领取腾讯云代金券