读书笔记:《算法图解》第一章 算法简介时间复杂度#

二分查找是对半查找,进队列表是有序时有效。

n个元素的列表,二分查找最多需要log2nlog2n 步,简单顺序查找最多需要n步。

对数#

对数:对数运算是幂运算的逆运算

N=ax(a>0,a≠1)N=ax(a>0,a≠1), xx就是aa为底NN的对数,记作x=logaNx=loga⁡N,其中:

  • aa : 底
  • NN : 真数
  • xx : 以aa为底NN的对数

幂:

log 指的都是 log2log2

log8log⁡8 = log28log2⁡8 = 3 (23=823=8)

  1. 以10为底的对数称为常用对数,记为lglg
  2. 以无理数ee(e=2.71828…e=2.71828…)为底的对数称为自然对数,记为lnln
  3. 零没有对数
  4. 实数范围内,负数没有对数;复数范围内,负数有对数

时间复杂度#

简单顺序查找的实践复杂度 O(n)O(n)

二分查找的时间复杂度 O(logn)O(log⁡n)

时间复杂度表示了最糟糕情况下的运行时间

常用时间复杂度#

  • O(logn)O(log⁡n) 对数时间
  • O(n)O(n) 线性时间
  • O(n×logn)O(n×log⁡n)
  • O(n2)O(n2)
  • O(n!)O(n!) n的阶乘

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 二分查找题目分析代码

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组...

912
来自专栏武培轩的专栏

剑指Offer-二进制中1的个数

package Other; /** * 二进制中1的个数 * 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 */ public c...

2564
来自专栏Venyo 的专栏

HttpServletRequest.getParameter()出现乱码现象解决方案

一、首先在项目中添加一个过滤器类,用来将所有参数转化为指定格式(UTF-8) import java.io.IOException;   import java...

38711
来自专栏用户画像

7.4.2 选择排序之堆排序

堆排序是一个树形选择排序方法,它的特点是:在排序过程中,将L[1...n]看成是一棵完全二叉树的顺序存储结构,

764
来自专栏Java Web

数据结构与算法(4)——优先队列和堆什么是优先队列?堆和二叉堆LeetCode相关题目整理

听这个名字就能知道,优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优...

3861
来自专栏老马说编程

(55) 容器类总结 / 计算机程序的思维逻辑

从38节到54节,我们介绍了多种容器类,本节进行简要总结,我们主要从三个角度进行总结: 用法和特点 数据结构和算法 设计思维和模式 用法和特点 我们在52节...

2237
来自专栏F_Alex

数据结构与算法(五)-线性表之双向链表与双向循环链表

前言:前面介绍了循环链表,虽然循环链表可以解决单链表每次遍历只能从头结点开始,但是对于查询某一节点的上一节点,还是颇为复杂繁琐,所以可以在结点中加入前一个节点的...

1492
来自专栏于晓飞的专栏

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。

972
来自专栏JavaEdge

LinkedHashMap源码分析(基于Java8)概要示例代码节点构造函数增删查遍历

4165
来自专栏desperate633

LeetCode 38. Count and Say题目分析代码

看过去这道题,好像很复杂,其实仔细分析,会发现思路很清晰。不管算第几个数,我们都要从第一个数算起,每个数都要根据前一个数算出来。算数的过程就两个点,一个计算co...

781

扫码关注云+社区

领取腾讯云代金券