【算法】二分查找和大O表示法

叁歲伎倆 2022-01-19 05:19 265阅读 0赞

## 场景 ##

### 电话本 ###

*  假设从电话本里面找 youjie 的电话，最常见的不是从开头开始找，而是从中间开始查找
 *  电话本是有序列表

### 1-100 猜想 ###

> 想起来小时候看过诸葛亮的一个虚构小故事。一次诸葛亮在军营里被军士质疑是不是真的很聪明。诸葛亮说你在1-1000里随便想个数字说出来，我能在10次以内猜到它。那么怎样以目标最少的次数猜到这个数字？

#### 简单查找 ####

*  如果从 1 开始猜，这叫简单查找，换句话说就是傻找
 *  如果是 99，那么得猜 99 次（临界点就是这个数）

#### 二分查找 ####

*  如果从中间值开始猜
 *  那么临界点就是 99，最坏的情况下只用猜七次，50 错，75 错..这样猜

那么得出结论，对于 n 个元素，用二分查找最多需要 log2（n） 步，简单查找最多需要 n 步

> 2^log2 （n）=n，log 叫对数运算，2^n 叫幂运算，他们互为逆运算

## 算法实现 ##

> 注意二分查找法必须是有序的，简单来说就是分一半

## 大 O 表示法 ##

> 指出的是最糟情况下的运行时间，也可以说是操作数

*  这里用大 O 表示法讨论运行时间，都是讨论的最糟糕的临界值，比如简单查找 100 个元素，就是要看每一个元素。二分查找也是查看最远的，那么就只用查看 log100 个元素约为 7
 *  log 时间这里的底数默认是 2，也就是默认是 log2
 *  其实我们是用幂运算的眼光来看，我们求的运行时其实就是指数

### 概念 ###

*  大 O 表示法指出了算法有多快。例如，假设列表包含 n 个元素，简单查找需要检查每个元素，因此需要执行 n 次查找,运行时间位 O（n）
 *  O(n),单位不是秒，大 O 表示法指的并不是以秒为单位的速度，而是能够比较操作数，它指出了算法运行时间的增速
 *  所以 n 是操作数的意思
 *  谈论算法的速度，是随着输入的增加，其运行事件将以怎么样的速度增加

### 常见的大 O 运行时间 ###

> 由快到慢的经常遇到的五种，可以自己想象一下坐标系图

*  O（log n）,也叫对数时间，这样的算法包括二分查找
 *  O(n)，线性时间，包括简单查找
 *  O(n\*log n)，包括快速排序（业界俗称快排），一种速度较快的快速排序
 *  O（n^ 2）,包括选择排序，一种速度较慢的排序算法
 *  O（n！），包括旅行商问题的解决方案，一种非常慢的算法

#### 旅行商问题 ####

> 旅行商要前往 5 个城市，同时确保旅程最短，这样它要每个城市都去，然后计算总旅程，再挑选路线最短的

*  5 个城市有 120 种不同的排列方式，因此需要 120 次操作
 *  这是一个非常非常慢的算法，但是这个问题也是计算机科学领域待解决的问题

转载于:https://juejin.im/post/5c853d8e5188257e5b2be2dd

发表评论取消回复

表情：

评论列表（有 0 条评论，265人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构和算法：大 O 表示法

介绍大 O 表示法是一种形式化模糊计数的方法。它使我们能够正式讨论算法的运行时间如何随着输入的增长而增长。它用于分析算法的性能。一个性能良好的算法是：

今天药忘吃喽~/ 2023年10月14日 21:14/ 0 赞/ 58 阅读

相关【算法专项二】二分查找法

简介二分查找法，是两大基础算法类别中最典型的一种（排序与搜索）。简单来说，二分搜索通过不断划分取中间点划分区间，以此在极大程度上减少查找的次数。不过二分查找的前提，

野性酷女/ 2023年01月20日 12:56/ 0 赞/ 19 阅读

相关算法的时间复杂度表示法(大O表示法)

大 O 复杂度表示法算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？ for a in

今天药忘吃喽~/ 2022年11月21日 01:06/ 0 赞/ 257 阅读

相关 big O notation - 大 O 表示法

big O notation - 大 O 表示法 Big O notation (with a capital letter O, not a zero), also c

╰+哭是因爲堅強的太久メ/ 2022年10月29日 03:11/ 0 赞/ 257 阅读

相关算法二分查找法BinarySearch

算法二分查找法BinarySearch 1. 二分查找法概述 2. 二分查找法实现 1. 二分查找法概述二分查找也称折半查找（Binary Sea

谁借莪１个温暖的怀抱￠/ 2022年10月13日 12:34/ 0 赞/ 220 阅读

相关大O表示法初学者指南

大O表示法初学者指南原文地址：[https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/][h

左手的ㄟ右手/ 2022年07月16日 14:56/ 0 赞/ 247 阅读

相关 [查找算法]二分查找法

二分查找法是经典的入门算法,以高效和广泛应用而著称. 算法是由静态方法rank() 实现的，它接受一个整数键和一个已经有序的int 数组作为参数。如果该键存在于数组中

「爱情、让人受尽委屈。」/ 2022年02月22日 02:49/ 0 赞/ 328 阅读

相关简说大O表示法

大O表示法：算法的时间复杂度通常用大O符号表述，定义为T\[n\] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。如果一个问题的规模是n

旧城等待，/ 2022年02月20日 01:11/ 0 赞/ 384 阅读

相关【算法】二分查找和大O表示法

场景电话本假设从电话本里面找 youjie 的电话，最常见的不是从开头开始找，而是从中间开始查找电话本是有序列表 1-100 猜想 > 想

叁歲伎倆/ 2022年01月19日 05:19/ 0 赞/ 266 阅读

相关算法复杂度和大O表示法

概念算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。时间复杂度一个算法执行所耗费的时间，从理论上是不能算出来的，必须

我不是女神ヾ/ 2021年09月20日 11:20/ 0 赞/ 309 阅读