专栏首页编程直播室读书笔记:《算法图解》第一章 算法简介时间复杂度#

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

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

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 条评论
登录 后参与评论

相关文章

  • 编程直播室第一期结束和第二期预告附录

    孙亖
  • 编程星球——水·滴创刊号 20180514

    孙亖
  • 中小学生Python课程第一阶段10课

    孙亖
  • C++多线程-多核编程

    多核编程并不是最近才兴起的新鲜事物。早在intel发布双核cpu之前,多核编程已经在业内存在了,只不过那时候是多处理器编程而已。为了实现多核编程,人们开发实现了...

    cwl_java
  • 小程序初学者必读——小程序的简单入门

    腾讯NEXT学位
  • 遇到中年「油腻男」?憋说话!直接甩他这 4 个小程序

    最近,一篇有关「油腻的中年男」的文章引爆朋友圈,文中总结了油腻的中年男的一些特点,比如戴各种串、有大肚子等。

    知晓君
  • 什么叫给密码“加盐”?如何安全的为你的用户密码“加盐”?

    在面对这个网络世界的时候,密码安全总是各个公司和用户都非常关心的一个内容,毕竟现在大家不管是休闲娱乐还是学习购物都是通过网上的帐号来进行消费的,所以我们通常会给...

    硬核项目经理
  • 5分钟开发一个物联网小程序【IoT迷你赛】

    2、登录腾讯云物联网开发平台https://console.cloud.tencent.com/iotexplorer

    用户1400606
  • 我的奇葩面试经历分享:喊价25K,HR 却给了30K

    本文是楼主前两个月 N 家公司的面试经历,总结复盘了面试现场,个人认为干货还是不少,在此和大家分享。

    美的让人心动
  • 教育培训机构如何通过小程序将流量最大化?

    自从2017年1月9日第一批小程序上线以来,“小程序”这个词就一直处在风口上,截止2018年6月30日,微信小程序数量已经突破100万,日活高达2.8亿。相对于...

    用户1745481

扫码关注云+社区

领取腾讯云代金券