算法题代码运行时间复杂度估计

2024-05-06 06:52

本文主要是介绍算法题代码运行时间复杂度估计,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

总结一下关于问题规模(n大小)与算法时间复杂度要求的关系,有时候通过问题规模就可以判断出这道题需要用什么算法。
这样判断的一个好处就是可以很自然地从暴力求解的思路入手,逐步展开优化,更符合实际编程环境下的思维习惯,毕竟在实际开发时很少会真的直接想到用双指针或者动态规划解决一个编程问题。

所以一般给出n的范围的地方都叫做’提示’

CPU的GHz的含义

目前CPU的执行频率单位都是GHz,大概意思可以看作一秒能够执行 1 0 9 10^9 109行代码,即一秒运行一亿次的指令。虽然不同型号的CPU有所差距,但是按照大O时间复杂度估计法的原则可以简单这么认为。

算法题n的量级

按照CPU一秒可以运行一亿次估算,假设题目中n的范围是 1 0 5 10^5 105,那么这道题用 O ( n 2 ) O(n^2) O(n2)的时间复杂度求解就会超过一秒,可以把超过一秒这个限制看作是题目要求的上限。因此只能选择用双指针、队栈、动态规划等进行优化。

n的大小与时间复杂度的大致对应关系

n 的量级时间复杂度一般场景
四万或者五万 O ( n ) O(n) O(n)双指针、动态规划、队栈
两万或三万 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))排序、贪心
几千 O ( n 2 ) O(n^2) O(n2)暴力
几十或者一两百 O ( n k ) O(n^k) O(nk) 或者 O ( 2 n ) O(2^n) O(2n)二叉树、回溯

可以粗略地按照万、千、百、十的数量级进行大致的判断。
基本上万级别即以上的都需要上算法了。

这篇关于算法题代码运行时间复杂度估计的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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