【阅读笔记】——时间复杂度

keithxiaoy 发布于2019-08-23 11:28 / 389人阅读

摘要：时间复杂度场景一一根长寸的面包，每天吃掉一寸，那么吃完整个面包需要几天答案自然是天可以记作场景二一根寸的面包，每天吃掉剩余的一半，吃的只剩下寸，需要多少天答案以为底，的对数，简写成，所以为天可以记作场景三每天吃掉一个鸡腿，那么吃掉整个鸡腿需

时间复杂度

场景一：一根长10寸的面包，每3天吃掉一寸，那么吃完整个面包需要几天？
答案自然是：3×10=30天
可以记作：T(n) = 3n

场景二：一根16寸的面包，每5天吃掉剩余的一半，吃的只剩下1寸，需要多少天？
答案：以2为底，16的对数，简写成log16，所以为 5×log16 = 20天
可以记作： T(n) = 5logn

场景三：每2天吃掉一个鸡腿，那么吃掉整个鸡腿需要多少天？
答案：2天
可以记作：T(n) = 2

场景四：一根长10寸的面包，吃掉第一个一寸需要1天，吃掉第二个1寸需要2天，吃完整个面包需要多少天？
答案：从1累加到10，共55天
可以记作：T(n) = 0.5n^2+0.5n

这四个场景分别是：线性式、对数式、常量式、多项式

渐进时间复杂度：

比如算法A的相对时间是 T(n)=100n，算法B的相对时间是T(n)=5n^2，到底哪个运行时间长呢？这要看n的取值

官方定义：

若存在函数 f(n)，使得当 n 趋近于无穷大时，T(n)/f(n) 的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数
记作 T(n)=O(f(n)) 称为O(f(n))为算法的渐进时间复杂度，简称时间复杂度，渐进时间复杂度用大写 O 表示，所以也被称为大O表示法

如何推导出时间复杂度，有如下几个原则：

如果运行时间是常数量级，用常数 1 表示

只保留时间函数中的最高阶项

如果最高阶项存在，则省去最高阶项前面的系数

回头看上面四个场景


T(n) = 3n	->	T(n) = O(n)
T(n) = 5logn	->	T(n) = O(logn)
T(n) = 2	->	T(n) = O(1)
T(n) = 0.5n^2+0.5n	->	T(n) = O(n^2)

文章：什么是时间复杂度？

云服务器 GPU云服务器时间复杂度快速排序时间复杂度最大流算法时间复杂度数据结构时间复杂度

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96995.html

前端阅读笔记 2016-11-25

摘要：为了防止某些文档或脚本加载别的域下的未知内容，防止造成泄露隐私，破坏系统等行为发生。模式构建函数响应式前端架构过程中学到的经验模式的不同之处在于，它主要专注于恰当地实现应用程序状态突变。严重情况下，会造成恶意的流量劫持等问题。今天是编辑周刊的日子。所以文章很多和周刊一样。微信不能发链接，点了也木有用，所以请记得阅读原文~ 发个动图娱乐下：使用 SVG 动画制作游戏使用 GASP ...

KoreyLee 2019-08-20 12:32 评论0 收藏0
学习笔记 | HTML 基本结构和基本标签 ——前端学习第一步！

摘要：基本结构语言中，一个页面是由四个部分组成文档声明标签对标签对标签对图示文档声明这是一个文档声明，表示这是一个页面。标签标签表示页面内容的范围。 HTML HTML ...

sPeng 2021-09-30 09:48 评论0 收藏0
Koa源码阅读笔记(4) -- ctx对象

摘要：本笔记共四篇源码阅读笔记源码阅读笔记源码阅读笔记服务器启动与请求处理源码阅读笔记对象起因前两天终于把自己一直想读的源代码读了一遍。首先放上关键的源代码在上一篇源码阅读笔记服务器启动与请求处理中，我们已经分析了的作用。本笔记共四篇Koa源码阅读笔记(1) -- coKoa源码阅读笔记(2) -- composeKoa源码阅读笔记(3) -- 服务器の启动与请求处理Koa源码阅读笔记(4...

ityouknow 2019-08-22 10:34 评论0 收藏0
【笔记】你不知道的JS读书笔记——异步

摘要：异步请求线程在在连接后是通过浏览器新开一个线程请求将检测到状态变更时，如果设置有回调函数，异步线程就产生状态变更事件，将这个回调再放入事件循环队列中。基础：浏览器 -- 多进程，每个tab页独立一个浏览器渲染进程（浏览器内核）每个浏览器渲染进程是多线程的，主要包括：GUI渲染线程 JS引擎线程也称为JS内核，负责处理Javascript脚本程序。（例如V8引擎） JS引擎线程负...

junnplus 2019-08-22 15:43 评论0 收藏0
靡不有初，鲜克有终——写在VNote半周岁

摘要：舒适的编辑体验通过语法高亮，最大地消除与生俱来的编辑和阅读的割裂感。所以，是不是又少了一个回到阅读模式的借口代码块语法高亮通过插件可以支持代码块里面的代码语法高亮，其他的编辑器好像没有支持。首发于简书. showImg(https://segmentfault.com/img/remote/1460000009164987); 从去年的十一开始到今天，VNote已经半周岁了，也迭代到...

roland_reed 2019-06-28 10:21 评论0 收藏0