本文主要是介绍算法题代码运行时间复杂度估计,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
总结一下关于问题规模(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) | 二叉树、回溯 |
可以粗略地按照万、千、百、十的数量级进行大致的判断。
基本上万级别即以上的都需要上算法了。
这篇关于算法题代码运行时间复杂度估计的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!