函数渐近界与算法性能分析_渐进下界怎么求_梦未的博客-程序员宅基地

技术标签：算法 # 数据结构与算法数学

渐近界与渐进函数简介

函数渐近界实际上算是一个集合，用来表示函数的边界或范围的集合

可以按大小/量级区分为：上界（高阶），平均界（同阶），下界（低阶）

再根据是否渐进区分（有没有可能相等）

一般来讲，用于表示函数渐近界的渐进符号有五个：

平均界（average bound）/渐进确界（asymptotically tight bound）：θ
渐进上界（upper bound）：O
渐进下界（lower bound）：Ω
非渐进紧确上界：o
非渐进紧确下界：ω

注释

$o (g (x))$ 是一个集合, 所以实际上 $\in o(g(x))$

通常我们记作 $f (x) = o (g (x))$ 以表达相同的概念, 其它几个记号同理.

可以理解为：

$\Longrightarrow f(x) \leq g(x)$
$\Longrightarrow f(x) < g(x)$
$f(x)=\Omega(g(x)) \Longrightarrow f(x) \geq g(x)$
$f(x)=\omega(g(x)) \Longrightarrow f(x) > g(x)$
$f(x)=\theta(g(x)) \Longrightarrow f(x) \approx g(x)$

高等数学中的例子

举一个高等数学中的例子：

$\alpha(x)$ 是 $\beta(x)$ 的高阶无穷小，也就是 $\displaystyle{\lim\limits{\frac{\alpha(x)}{\beta(x)}}=0}$

那么记为： $\alpha(x)=o(\beta(x))$ ，可以理解为 $\beta(x)$ 是 $\alpha(x)$ 的非渐进紧确上界

函数阶的例子

再以函数阶举例：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SL7UayQ2-1673949573802)(https://image.dreature.xyz/images/post/image-2022609215309-1654785393614.png)]

任取图上两个函数 $a = f (n)$ 和 $b = g (n)$ ，只要 $a$ 在 $b$ 的左边，那都可以说：

$a = O (b)$ 或 $a = o (b)$
$b=\Omega(a)$ 或 $b=\omega(a)$

运用于算法性能分析

渐近界的概念经常被用于算法性能分析中，当参数 $n$ 趋于无穷的时候，各个算法（函数）孰优孰劣一看便知

对于两个算法的成本函数（时间、空间等） $f (n)$ 和 $g (n)$ ，谁更低阶谁性能更优

若 $\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=c$ ，则 $f(n)=\theta(g(n))$ ，二者性能相当
若 $\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=0$ ，则 $f (n) = o (g (n))$ ， $f (n)$ 算法更优
若 $\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=\infty$ ，则 $f(n)=\omega(g(n))$ ， $g (n)$ 算法更优

比如对于冒泡排序算法而言

冒泡排序伪代码

（输入N个待排序的数，其中的第i个数可用a[i]表示）
定义一个i，i的值从N到2递减，对于每个i:
         定义一个j，j的值从1到i-1递增，对于每个j：
                  如果a[j]>a[j+1]：
                          将a[j]和a[j+1]的值交换

冒泡排序流程图

冒泡排序过程动图

冒泡的平均时间复杂度是 $O(n^2)$ ，这意味着排序 $n$ 个数据，平均需要耗费 $n^2$ 量级的时间

其他算法的复杂度如下图

本文链接：https://blog.csdn.net/weixin_42077074/article/details/125212841

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Visual Studio制作小型计算器_chouherou4683的博客-程序员宅基地

打开Visual Studio工具，新建一个window应用窗体。步骤如下：确定后出现了我们第一个窗体Form1。我们就在这制作小型计算器，出现的界面如下：修改下form1的名称。右键上面的窗体打开属性，找到Text属性，把form1改为...

C语言函数与模块化程序设计_大暑这天开通了博客的博客-程序员宅基地

1.函数的定义1.函数的分类（1）标准库函数（2）自定义函数2.函数的定义自定义的一系列函数。一般形式：返回值类型函数名（类型形式参数1 ，类型形式参数2，。。。）|声明语句序列可执行语序序列|函数定界符–花括号 { }，函数内部定义的变量只能再函数体内访问，称为内部变量。头部参数里面的变量，称为形式参数。2.向函数传递和从函数返回值1.函数的调用（1)函数必须通过main（）间接或者直接发挥作用。因此就涉及到函数调用的问题。main 函数调用时必须提供一个称为实际参

win8和ubuntu双系统相互引导的问题_jumping_frog的博客-程序员宅基地

泪奔了，我的win8和ubuntu爽系统

django用户邮箱激活流程_The Winslow Accord的博客-程序员宅基地

1.在setting.py中添加配置邮箱信息：EMAIL_BACKEND = ‘django.core.mail.backends.smtp.EmailBackend’EMAIL_HOST = ‘smtp.163.com’ #服务器EMAIL_PORT = 25 #端口，一般情况下都为25EMAIL_HOST_USER = ‘[email protected]’ ...

launch文件用法_lichunhong000的博客-程序员宅基地

launch文件用法https://www.cnblogs.com/CZM-/p/5943821.htmllaunch 在ROS应用中，每个节点通常有许多参数需要设置，为了方便高效操作多个节点，可以编写launch文件，然后用roslaunch命令运行 roslaunch: roslaunch [options] [package] [arg_name:=value…] rosla...

ConneR and the A.R.C. Markland-N--- codeforces1293A_fisht ank的博客-程序员宅基地

A.R.C. Markland-N is a tall building with n floors numbered from 1 to n. Between each two adjacent floors in the building, there is a staircase connecting them.It’s lunchtime for our sensei Colin “Co...

随便推点

关于付费专栏订阅模式调整的说明_csdn付费专栏文章设置为试读什么意思_LaoYuanPython的博客-程序员宅基地

老猿目前开通了2个付费专栏，付费专栏《使用PyQt开发图形界面Python应用》专门介绍基于Python的PyQt图形界面开发基础教程，付费专栏《moviepy音视频开发专栏》详细介绍moviepy音视频剪辑合成处理的类相关方法及使用相关方法进行相关剪辑合成场景的处理，都适合有一定Python基础但无相关专利知识的小白读者学习。这2个收费专栏以前在CSDN上只需订阅一次即都可以阅读，最近CSDN的版本进行了更新，支持分专栏订阅，因此老猿的付费专栏在10月10日进行了订阅模式调整，订购分专栏进行，订购哪个专