Nemo
Nemo
《算法图解》-第一章:二分查找和大O表示法
《算法图解》-第一章:二分查找和大O表示法

本章内容

  • 编写第一种查找算法:二分查找
  • 学习如何谈论算法的运行时间:大O表示法
  • 了解一种常用的设计方法:递归

什么是算法?

  • 算法是一组完成任务的指令,任何代码片段都可以视为算法。

二分查找

  • 二分查找是一种算法,其输入是一个有序的元素列表(仅当列表有序的时候,二分查找才管用)。如果要查找的元素包含在列表中,二分查找返回其位置,否则返回null。
首先介绍简单查找

简单查找就是‘傻找’,例如猜测一个1~100的数字,从1开始依次往上猜,每次猜测只能排除一个数字。如果数字是99,则需要猜测99次才能猜到。

二分查找
  • 而二分查找法则从50开始,一下子可以排除一半的数字;每次都猜测中间的数字,从而每次都将剩余的数字排除一半。

  • 一般而言,对于包含n个元素的列表,用二分查找最多需要[latex]\log n[/latex]步,而简单查找最多需要n步。

二分查找Python代码实现
def binary_search(list, item):
    low = 0
    high = len(list) - 1 
    while low <= high: #只要范围没有缩小到只包含一个元素,就检查中间的元素
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item: #找到元素了
            return mid
        if guess > item: #猜的值大了
            high = mid - 1
        else: #猜的值小了
            low = mid + 1
    return None #没有猜测的值


list = [1, 2, 3, 4, 5, 6, 7]

# 能找到对应的值
print(binary_search(list, 3))
print(binary_search(list, 6))

# 不能找到对应的值
print(binary_search(list, 8))

leetcode中的二分查找

运行时间

  • 线性时间(linear time):以简单查找为例,最多的猜测次数与列表长度相同,这被称为线性时间-O(n)。
  • 对数时间(log时间)::比如二分查找-O(log n).

线性时间和对数时间的增速不同!

大O表示法

大O表示法是一种特殊的表示法,指出了算法的速度有多快,同时也表示了算法的增速的差异,其单位并不是秒,而是操作数,指出了最糟糕情况下的运行时间。

一些常见的大O运行时间

从快到慢:
O(log n) 对数时间,如二分查找
O(n) 线性时间,如简单查找
O(n * log n ) 线性对数时间,如快速排序
O([latex]n^{2}[/latex]) 平方时间,如选择排序
O(n!) 阶乘时间,如旅行商问题

小结
  • 算法的速度指的并非时间,而是操作数的增速
  • 谈论算法的速度时,我们说的是随着输入的增加,其运行时间将以什么样的速度增加。
  • 算法的运行时间用大O表示法表示
  • O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快的越多。
赞赏
Nemo版权所有丨如未注明,均为原创丨本网站采用BY-NC-SA协议进行授权,转载请注明转自:https://kanghaov.com/74.html
https://secure.gravatar.com/avatar/9fd8359b8faa6f7789f9623ba6041e4a?s=256&d=monsterid&r=g

kanghaov

文章作者

推荐文章

发表评论

textsms
account_circle
email

Nemo

《算法图解》-第一章:二分查找和大O表示法
本章内容 编写第一种查找算法:二分查找 学习如何谈论算法的运行时间:大O表示法 了解一种常用的设计方法:递归 什么是算法? 算法是一组完成任务的指令,任何代码片段都可以视为…
扫描二维码继续阅读
2019-05-12