算法:渐进记号的含义及时间复杂度计算

2024-06-23 04:44

本文主要是介绍算法:渐进记号的含义及时间复杂度计算,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

渐进记号及时间复杂度计算

渐近符号

渐近记号 Ω \Omega Ω

   f ( n ) = Ω ( g ( n ) ) f(n)=\Omega(g(n)) f(n)=Ω(g(n)) 当且仅当存在正的常数C和 n 0 n_0 n0,使得对于所有的 n ≥ n 0 n≥ n_0 nn0 ,有 f ( n ) ≥ C ( g ( n ) ) f(n)≥C(g(n)) f(n)C(g(n))。此时,称 g ( n ) g(n) g(n) f ( n ) f(n) f(n)的下界。
  根据符号 Ω \Omega Ω的定义,用它评估算法的复杂度得到的是问题规模充分大时的一个下界。这个下界的阶越高,评估越精确,越有价值。

例:设 f ( n ) = n 2 + n f(n)=n^2+n f(n)=n2+n,则
f ( n ) = Ω ( n 2 ) f(n)=\Omega(n^2) f(n)=Ω(n2),取 c = 1 , n 0 = 1 c=1,n_0=1 c=1,n0=1 即可
f ( n ) = Ω ( 100 n ) f(n)=\Omega(100n) f(n)=Ω(100n),取 c = 1 / 100 , n 0 = 1 c=1/100,n_0=1 c=1/100,n0=1 即可
显然, Ω ( n 2 ) \Omega(n^2) Ω(n2)作为下界更为精确。

渐进记号 Θ \Theta Θ

   f ( n ) = Θ ( g ( n ) ) f(n)=\Theta(g(n)) f(n)=Θ(g(n)) 当且仅当存在正常数和 C 1 , C 2 , n 0 C_1,C_2,n_0 C1,C2,n0,使得对于所有的 n ≥ n 0 n≥n_0 nn0, 有 C 1 ( g ( n ) ) ≤ f ( n ) ≤ C 2 ( g ( n ) ) C_1(g(n))≤f(n)≤ C_2(g(n)) C1(g(n))f(n)C2(g(n))。此时,称 f ( n ) f(n) f(n) g ( n ) g(n) g(n)同阶。
  这种渐进符号是指,当问题规模足够大的时候,算法的运行时间将主要取决于时间表达式的第一项,其它项的执行时间可以忽略不计。第一项的常数系数,随着n的增大,对算法的执行时间也变得不重要了。

例: 3 n + 2 = Θ ( n ) 3n+2= Θ(n) 3n+2=Θ(n)
10 n 2 + 4 n + 2 = Θ ( n 2 ) 10n^2+4n+2= Θ(n^2) 10n2+4n+2=Θ(n2)
5 × 2 n + n 2 = Θ ( 2 n ) 5×2^n+n^2= Θ(2^n) 5×2n+n2=Θ(2n)

渐进记号小 ο \omicron ο

   f ( n ) = ο ( g ( n ) ) f(n)=\omicron(g(n)) f(n)=ο(g(n))当且仅当 f ( n ) = ο ( g ( n ) ) f(n)=\omicron(g(n)) f(n)=ο(g(n)) g ( n ) ≠ ο ( f ( n ) ) g(n)\neq \omicron(f(n)) g(n)=ο(f(n)),此时, g ( n ) g(n) g(n) f ( n ) f(n) f(n)的一个绝对上界。
  小 ο \omicron ο提供的上界可能是渐近紧确的,也可能是非紧确的。(如: 2 n 2 = ο ( n 2 ) 2n^2=\omicron(n^2) 2n2=ο(n2)是渐近紧确的,而 2 n = ο ( n 2 ) 2n=\omicron(n^2) 2n=ο(n2)是非紧确上界。

例: 4 n l o g n + 7 = ο ( n 2 ) 4nlogn + 7= \omicron(n^2) 4nlogn+7=ο(n2)

渐进记号小 ω \omega ω

   f ( n ) = ω ( g ( n ) ) f(n)=\omega(g(n)) f(n)=ω(g(n))当且仅当 f ( n ) = ω ( g ( n ) ) f(n)=\omega(g(n)) f(n)=ω(g(n)) g ( n ) ≠ ω ( f ( n ) ) g(n)\neq \omega(f(n)) g(n)=ω(f(n)),此时, g ( n ) g(n) g(n) f ( n ) f(n) f(n)的一个绝对下界。
   ω \omega ω表示一个非渐进紧确的下界。

例: f ( n ) = n 2 + n f(n)=n^2+n f(n)=n2+n,则 f ( n ) = f(n)= f(n)=\omega ( n ) (n) (n)是正确的, f ( n ) = f(n)= f(n)=\omega ( n 2 ) (n^2) (n2)是错误的。

渐进记号大 O \Omicron O

  设 f ( n ) f(n) f(n) g ( n ) g(n) g(n) 是定义域为自然数集上的函数。若存在正数 c c c n 0 n_0 n0c和n_0c,使得对一切 n ≥ n 0 n≥ n_0 nn0 都有 0 ≤ f ( n ) ≤ c g ( n ) 0 ≤ f(n) ≤ cg(n) 0f(n)cg(n)成立,则称 f ( n ) f(n) f(n)的渐进的上界是 g ( n ) g(n) g(n),记作 f ( n ) = O g ( n ) f(n)=\Omicron g(n) f(n)=Og(n)
  根据符号大 O \Omicron O的定义,用它评估算法的复杂度得到的只是问题规模充分大时的一个上界。这个上界的阶越低,评估越精确,越有价值。

例:设 f ( n ) = n 2 + n f(n)=n^2+n f(n)=n2+n,有
f ( n ) = O ( n 2 ) f(n)=\Omicron(n^2) f(n)=O(n2),取 c = 2 , n 0 = 1 c=2,n_0=1 c=2,n0=1即可
f ( n ) = O ( n 3 ) f(n)=\Omicron(n^3) f(n)=O(n3),取 c = 1 , n 0 = 2 c=1,n_0=2 c=1,n0=2即可

常见的时间复杂度关系

O(1)<O(log(n))<O(n)<O(nlogn)<O(n^{2})

   O ( 2 n ) O(2^{n}) O(2n) O ( n ! ) O(n!) O(n!)大于以上的所有时间复杂度,具体原因参考图像。

时间复杂度计算:递归方程

  加、减、乘、除、比较、赋值等操作,一般被看作是基本操作,并约定所用的时间都是一个单位时间;通过计算这些操作分别执行了多少次来确定程序总的执行步数。一般来说,算法中关键操作的执行次数决定了算法的时间复杂度。
  比较简单的算法时间复杂性估计通常需要观察在for、while循环中的关键操作执行次数,在这里我们只讨论一种比较复杂的时间复杂度计算问题:求递归方程解的渐近阶的方法。递归式就是一个等式,代表了递归算法运算时间和n的关系,通过更小输入的函数值来描述一个函数。那么如何求得递归算法的Θ渐进界呢?主要有三种方法。

代入法

  代入法是指自己猜测一个界,然后用数学归纳法进行验证是否正确,这种猜测主要靠经验,不常用。

迭代法

  迭代法是指循环地展开递归方程,然后把递归方程转化为和式,使用求和技术解之。

套用公式法

  这个方法为估计形如: T ( n ) = a T ( n / b ) + f ( n ) T(n)=aT(n/b)+f(n) T(n)=aT(n/b)+f(n) 的递归方程解的渐近阶提供三个可套用的公式。要求其中的a≥1和b>1是常数,f(n)是一个确定的正函数。那么在三种情况下,我们可以得到T(n)的渐进估计式,懒得打公式,所以截图。
在这里插入图片描述

这篇关于算法:渐进记号的含义及时间复杂度计算的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1086225

相关文章

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python如何获取域名的SSL证书信息和到期时间

《Python如何获取域名的SSL证书信息和到期时间》在当今互联网时代,SSL证书的重要性不言而喻,它不仅为用户提供了安全的连接,还能提高网站的搜索引擎排名,那我们怎么才能通过Python获取域名的S... 目录了解SSL证书的基本概念使用python库来抓取SSL证书信息安装必要的库编写获取SSL证书信息

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

如何利用Java获取当天的开始和结束时间

《如何利用Java获取当天的开始和结束时间》:本文主要介绍如何使用Java8的LocalDate和LocalDateTime类获取指定日期的开始和结束时间,展示了如何通过这些类进行日期和时间的处... 目录前言1. Java日期时间API概述2. 获取当天的开始和结束时间代码解析运行结果3. 总结前言在J