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

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

相关文章

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

Feign Client超时时间设置不生效的解决方法

《FeignClient超时时间设置不生效的解决方法》这篇文章主要为大家详细介绍了FeignClient超时时间设置不生效的原因与解决方法,具有一定的的参考价值,希望对大家有一定的帮助... 在使用Feign Client时,可以通过两种方式来设置超时时间:1.针对整个Feign Client设置超时时间

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

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 使用时