时间复杂度big-O、Big-Omega和big-Theta
2024-08-30 04:38:09
我们有三种曲线:
A curve that we know is "above" the running time function when n is large. ( Big-O )
当n足够大时,曲线高于运行时间函数(big-o)
A curve that we know is "below" the running time function when n is large. (Big-Omega)
当n足够大时,曲线低于运行时间函数(big-omega)
If we can squeeze the curves that are "above" and "below" the running time function close enough, then we can figure out Big-Theta(big-theta)
Big-Theta 仅仅只是一个"Scaled"版本的运行曲线,big-theta仅仅只是scale最高序列的f(n)行为。big-theta仅仅只是一个曲线
Big-O 告诉你什么样的函数增长速度大于f(N)
Bit-Theta告诉你什么样的函数增长速度同f(N)
Big-Omega告诉你什么样的函数增长速度小于f(N)
Funcitons in Asymptotic notation
所有公式都可以用这个来表示
Logarithms grow more slowly than polynomials
对数比指数增长慢
接下来是指数增长的顺序(由慢到快):
It would be convenient to have a form of asymptotic notation that means
运行时间最多增长这么多,但它可以增长的更慢
big-O asymptotic upper bounds:渐近上界
best case average/expected case worst case
最新文章
- js指定标签的id只能添加不能删除
- Threads in Spring
- bzoj3717: [PA2014]Pakowanie
- 使用ImageMagick和Tesseract进行简单数字图像识别
- NGINX结合SHELL统计用户的UV及IP汇总
- 解决VS2010打开Web页面时经常由于内存较低而导致VS2010自动关闭的问题
- WINDOWS特有的消息常量标识符
- ASP.NET多文件批量打包下载
- vim命令:编辑模式和命令模式
- 【Swift 4.2】uuid 取 hashCode(与 Java/Go/Kotlin 一致)
- 利用 Windows API Code Pack 修改音乐的 ID3 信息
- java学习笔记-输入输出流
- JS回调函数--简单易懂有实例
- java 标签编译后没有显示
- [No0000F3]C# 结构(Struct)
- MYSQL 5.7修改密码,登录问题
- oneinstack远程管理数据库
- HTML5学习笔记(二十四):DOM扩展
- L1-005 考试座位号
- ros建立ospf邻居的条件
热门文章
- 第四章 文件的基本管理和XFS文件系统备份恢复 随堂笔记
- Java虚拟机(一)-Java内存区域
- 每天用SpringBoot,还不懂RESTful API返回统一数据格式是怎么实现的?
- 约会安排 HDU - 4553(线段树区间查询,区间修改,区间合并)
- 洛谷 P2158 [SDOI2008]仪仗队
- 帝国CMS(EmpireCMS) v7.5 代码注入分析(CVE-2018-19462)
- ASP.NET Core MVC 之过滤器(Filter)
- windows下用GCC编译DLL
- 【雕爷学编程】Arduino动手做(16)---数字触摸传感器
- 如何比较装X地回答问题 | 面试系列.1