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

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

相关文章

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

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

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

修改若依框架Token的过期时间问题

《修改若依框架Token的过期时间问题》本文介绍了如何修改若依框架中Token的过期时间,通过修改`application.yml`文件中的配置来实现,默认单位为分钟,希望此经验对大家有所帮助,也欢迎... 目录修改若依框架Token的过期时间修改Token的过期时间关闭Token的过期时js间总结修改若依