渐进性分析和算法复杂度

渐进性分析和算法复杂度

作者: 闪电侠悟空 | 来源:发表于2020-07-08 14:48 被阅读0次

渐进性分析和算法复杂度
算法
算法复杂度分析
数据结构-复杂度分析
时间复杂度和空间复杂度笔记
复杂度分析（上）
数据结构与算法学习-复杂度分析
算法复杂度分析与最大子串问题
数据结构与算法-复杂度分析
一个好的算法如何测评

1. 渐近线（直线）

曲线的渐近线

渐近线是曲线的一种性质，描述曲线在很远位置处的表现，属于高中课本知识;
通常是用直线 $y = g(x)$ 来描述曲线 $y= f(x)$ 在远处的性质; 也就是曲线 $f(x)$ 在很远处和直线 $f(x)$ 基本重合，（不严格的）数学上是: $\lim_{x\rightarrow +\infty} [f(x)-g(x)]\rightarrow 0$
问题：不是所有的曲线 $f(x)$ 都有直线的渐近线, 比如 $f(x)=x^2+x$ 。

2. 渐进曲线(同数量级曲线)

https://www.bilibili.com/video/BV1c741137Wf?from=search&seid=13836527270049512517

也是研究曲线 $f(x)$ 在很远处的表现，不过想用简单曲线逼近复杂曲线。看上图， $T_1(n)$ 即使乘以系数 $1.1$ ，按照渐近线定义的绝对距离也没法收敛，不能继续工作了，所以只能退而求其次，采用数量级上的分析。
通常是用简单曲线 $y = g(x)$ 来描绘曲线 $y= f(x)$ 在数量级上的表现; 数学上用: $\lim_{x\rightarrow +\infty} [\frac{f(x)}{g(x)}]$ 来度量。出现数量级上的三种比较结果（大，小，相等）。参考https://blog.csdn.net/chieryu/article/details/50432699
Big O, $O$ , 表示上界。用 $\lim_{x\rightarrow +\infty} [\frac{f(x)}{g(x)}]\rightarrow0$ （数量级上 $f(x)$ 大）或者 $\lim_{x\rightarrow +\infty} [\frac{f(x)}{g(x)}]\rightarrow c, c\neq0$ （数量级上 $f(x)$ 与 $g(x)$ 相同）表示函数 $f(x)$ 在很远处的数量级上的上界是 $g(x)$ 。这种表示太啰嗦，所以大家规定出记号。 $f(x)=O(g(x))$ , 上界.
类似，还有下界 $\Omega$ , $f(x)=\Omega(g(x))$ 。如果既是上界，又是下界，我们就可以说确界(或者紧界)关系 $f(x)=\Theta(g(x))$ .
在算法复杂度分析中，通常有 $O(n),O(n^2),O(nlog(n))$ ,等等。

相关文章

渐进性分析和算法复杂度
1. 渐近线（直线）渐近线是曲线的一种性质，描述曲线在很远位置处的表现，属于高中课本知识; 通常是用直线来描述...
算法
重拾算法：算法效率分析（一）（空间复杂度和时间复杂度）详解算法的各种复杂度的差别有多大（带图）算法复杂度选择...
算法复杂度分析
复杂度分析：数据结构和算法解决的两大问题：快和省。运行快，储存省。复杂度分析是算法学习的精髓：时间复杂度，空间...
数据结构-复杂度分析
为什么需要复杂度分析？复杂度分析实在太重要了。复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容...
时间复杂度和空间复杂度笔记
复杂度分析笔记复杂度主要分为时间和空间复杂度时间复杂度：算法（程序）执行的时间变化趋势空间复杂度：算法（程序...
复杂度分析（上）
复杂度分析（上）如何分析、统计算法的执行效率和资源消耗数据结构和算法解决的是快和省的问题复杂度分析是整个算...
数据结构与算法学习-复杂度分析
前言这一篇笔记主要记录总结了什么是算法复杂度？、为什要做算法复杂度分析？、如何做算法复杂度分析？、常用的复杂度级...
算法复杂度分析与最大子串问题
算法复杂度分析算法复杂度基本定义算法复杂度分析基于以下四条定义：如果存在常数c与$n_{0}$使$N \ge...
数据结构与算法-复杂度分析
时间、空间复杂度：衡量算法执行小路的指标，数据结构与算法离不开时间、空间复杂度分析，复杂度分析是算法的精髓。为什...
一个好的算法如何测评
一个算法的好坏可以根据复杂度分析来测评. 复杂度分析包括时间复杂度和空间复杂度. 1.时间复杂度需要考虑: 1)...

网友评论

本文标题：渐进性分析和算法复杂度

本文链接：https://www.haomeiwen.com/subject/vpgqcktx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

热点阅读

关于我们|服务条款|联系我们|渐进性分析和算法复杂度|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！