《算法图解》第一章笔记与课后练习_二分查找算法

软件环境: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 条评论
登录 后参与评论

相关文章

来自专栏超智能体

YJango:TensorFlow中层API Datasets+TFRecord的数据导入

2. 对接性:TensorFlow中也加入了高级API (Estimator、Experiment,Dataset)帮助建立网络,和Keras等库不一样的是:这...

47922
来自专栏大数据学习笔记

TensorFlow学习笔记:3、TensorFlow基本概念

TensorFlow学习笔记:3、TensorFlow基本概念 3.1 计算图与operation Tensor(张量)意味着N维数组,Flow(流)意味着基于...

22110
来自专栏人工智能LeadAI

TensorFlow从0到1丨第2篇:TensorFlow核心编程

上一篇Hello, TensorFlow!中的代码还未解释,本篇介绍TensorFlow核心编程的几个基本概念后,那些Python代码就很容易理解了。 与Ten...

3824
来自专栏null的专栏

机器学习算法实现解析——liblbfgs之L-BFGS算法

1、liblbfgs简介 liblbfgs是L-BFGS算法的C语言实现,用于求解非线性优化问题。 liblbfgs的主页:http://www.chokkan...

3806
来自专栏CNN

从Tensorflow模型文件中解析并显示网络结构图(pb模型篇)

Tensorflow官方提供的Tensorboard可以可视化神经网络结构图,但是说实话,我几乎从来不用。主要是因为Tensorboard中查看到的图结构太混乱...

3255
来自专栏章鱼的慢慢技术路

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

2094
来自专栏章鱼的慢慢技术路

笔试常考题型之时间复杂度

2446
来自专栏AI研习社

深度学习对话系统实战篇 -- 简单 chatbot 代码实现

本文的代码都可以到我的 github 中下载:https://github.com/lc222/seq2seq_chatbot 前面几篇文章我们已经介绍了 s...

6678
来自专栏漫漫深度学习路

pytorch学习笔记(九):PyTorch结构介绍

PyTorch结构介绍 对PyTorch架构的粗浅理解,不能保证完全正确,但是希望可以从更高层次上对PyTorch上有个整体把握。水平有限,如有错误,欢迎指错,...

2236
来自专栏书山有路勤为径

分治算法之归并排序

分治算法: 将一个规模为N的问题分解为K个规模较小的子问题,这些子问题互相独立且与原问题性质相同。求出子问题的解后进行合并,就可得到原问题的解。

491

扫码关注云+社区