我的创作纪念日--数据结构(四)——渐进时间复杂度

2023-12-12 22:28

本文主要是介绍我的创作纪念日--数据结构(四)——渐进时间复杂度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

😀前言
今天是我的创造256天有太多太多的感想和感谢了言不表意在文章体现吧

🏠个人主页:尘觉主页
在这里插入图片描述

🧑个人简介:大家好,我是尘觉,希望我的文章可以帮助到大家,您的满意是我的动力😉

在csdn获奖荣誉: 🏆csdn城市之星2名
⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ 💓Java全栈群星计划top前5
⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ 🤗 端午大礼包获得者
⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ 🥰阿里云专家博主
⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ 😉亚马逊DyamoDB结营

💕欢迎大家:这里是CSDN,我总结知识的地方,欢迎来到我的博客,感谢大家的观看🥰
如果文章有什么需要改进的地方还请大佬不吝赐教 先在次感谢啦😊

文章目录

  • 数据结构——渐进时间复杂度
    • 渐进时间复杂度
    • 分析算法时间复杂度的基本方法
      • 常数阶
      • 线性阶
      • 对数阶
      • 平方阶
      • 立方阶
    • 最好、最坏和平均时间复杂度
      • 计算公式
    • 算法的空间复杂度:算法要占据的空间
      • 时间与空间的取舍

数据结构——渐进时间复杂度

渐进时间复杂度

​ 对于稍微复杂一些的算法,计算出算法中所有语句的频度通常是比较困难的。通常,算法的执行时间是随问题规模增长而增长的,因此对算法的评价通常只需考虑其随问题规模增长的趋势。

这种情况下,我们只需要考虑当问题规模充分大时,算法中基本语句的执行次数在渐近意义下的阶。

image-20230916141845969

基本语句:执行次数最多;对算法运行时间贡献最大;嵌套最深的语句。

分析算法时间复杂度的基本方法

  1. 找出语句频度最大的那条语句作为基本语句;

  2. 计算基本语句的频度,得到问题规模n的某一个函数;

  3. 取其数量级用O表示

img

忽略所有低次幂项和最高次幂的系数,这样可以简化算法分析,也体现出了增长率的含义。

img

常数阶

img

实际上,如果算法的执行时间不随问题规模n的增加而增长,算法中语句频度就是某个常数。即使这个常数再大,算法的时间复杂度都是O(1)。

线性阶

给小羊一个长度为10cm小草,小羊每三分钟吃掉1cm小草,那么他吃掉整个小草要多久?

答案自然是3*10=30min

如果小草的长度为n cm呢?

此时吃掉整个小草需要3*n即3n分钟。

如果用一个函数来表达吃掉整个小草所需要的时间可以记作T(n)=3n(n表示小草的长度即处理的数据的规模)

对数阶

给小羊一个长度为16cm的小草,小羊小羊每5min吃掉小草剩余长度的一半,第1min吃掉8cm,第2min吃掉4cm,第三min吃掉2cm…那么小羊把小草吃得只剩下1cm,需要多少天呢?

这个问题翻译一下,就是数字16不断地除以2,除几次以后的结果等于1?这里要涉及到数学当中的对数,以2位底,16的对数,可以简写为log216。(下文对函数的底数全部省略)

因此,把小草吃得只剩下1寸,需要 5log16=54=20 min

如果小草的长度为n cm呢?

此时吃掉整个小草需要5logn分钟记作T(n)=5logn

image-20230916142527973

也可以给n几个具体的值找规律

平方阶

img

由于当i=0时内循环执行n次,当i=1时内循环执行n-1次,…,当i=n-1时内循环执行1次总执行次数n+(n-1)++(n-2)+…+1=n(n+1)/2

时间复杂度是O(n^2)

立方阶

image-20230916142820411

显见,该程序段中频度最大的语句是(5),这条最深层循环内的基本语句的频度,依赖于各层循环变量的取值,由内向外可分析出语句(5)的执行次数为:

img

最好、最坏和平均时间复杂度

有的情况算法的基本操作重复执行的次数还随问题输入的数据集不同而不同

img

最好的情况a0=e执行1次

最坏数组中没有e/an-1=e执行n次

而对于一个算法来说,需要考虑各种可能出现的情况,以及每一种情况出现的概率,一般情况下,可假设待查找的元素在数组中所有位置上出现的可能性均相同。类似于数学中求期望值。计算每一种情况执行次数与概率的乘积在求和。

  • 最坏时间复杂度是指在最坏情况下算法的的复杂度;
  • 最好时间复杂度是指在最好情况下算法的的复杂度;
  • 平均时间复杂度是指算法在所有可能情况下,按照输入实例以等概率出现时,算法计算量的加权平均值。

通常考虑最坏和平均但有时平均比较难计算只考虑最坏时间复杂度,最坏情况运行时间是一种保证,那就是运行时间不会再坏了。

计算公式

image-20230916142918940

image-20230916142926283

常见的时间复杂度按数量级递增排列依次为:

常量阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O( nlog2n)、平方阶O(n2)、立方阶O(n3) k次方阶O(nk)、指数阶O(2n)等。

如果时间复杂度是平方阶最好降低到对数阶实在不行平方阶也可以接受,立方阶也尚可。

算法的空间复杂度:算法要占据的空间

算法本身要占据的空间:输入/输出、指令、常数、变量等。

算法要使用的辅助空间

若输入数据所占据的空间只取决于问题本身和算法无关,这样只需分析该算法在实现时所需的辅助单元即可,若算法执行时所需的辅助单元相对于输入数据量而言是个常数,则称此算法为原地施工,空间复杂度为O(1)

img

时间与空间的取舍

​ 人们之所以花大力气去评估算法的时间复杂度和空间复杂度,其根本原因是计算机的运算速度和空间资源是有限的。就如一个大财主,基本不必为日常的花销而伤脑筋,而一个没有多少积蓄的普通人则不得不为日常的花销精打细算。对于计算机系统来说也是如此,虽然目前计算机的CPU处理速度不断飙升,内存和硬盘空间也越来越大,但是面对庞大而复杂的数据和业务,我们仍要精打细算,选择最有效的利用方式。

​ 举个例子说,要判断某年是不是闰年,你可能会花一点心思来写一个算法,每给一个年份,就可以通过这个算法计算得到是否闰年的结果。

​ 另外一种方法是,事先建立一个有2050个元素的数组,然后把所有的年份按下标的数字对应,如果是闰年,则此数组元素的值是1,如果不是元素的值则为0。这样,所谓的判断某一年是否为闰年就变成了查找这个数组某一个元素的值的问题。

​ 第一种方法相比起第二种来说很明显非常节省空间,但每一次查询都需要经过一系列的计算才能知道是否为闰年。第二种方法虽然需要在内存里存储2050个元素的数组,但是每次查询只需要一次索引判断即可。

​ 这就是通过一笔空间上的开销来换取计算时间开销的小技巧。到底哪一种方法好?其实还是要看你用在什么地方。但在绝大多数情况下,时间复杂度更重要一些,我们宁愿多分配一些内存空间也要提升程序的执行速度。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

这篇关于我的创作纪念日--数据结构(四)——渐进时间复杂度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

python处理带有时区的日期和时间数据

《python处理带有时区的日期和时间数据》这篇文章主要为大家详细介绍了如何在Python中使用pytz库处理时区信息,包括获取当前UTC时间,转换为特定时区等,有需要的小伙伴可以参考一下... 目录时区基本信息python datetime使用timezonepandas处理时区数据知识延展时区基本信息

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

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

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

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

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

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

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

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

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

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