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

阅读量：

就这个问题而言，在很多时候我们都可以通过分析问题规模(n的大小)来初步确定适合的算法类型。这种判断方式的一个显著优势在于能够引导我们自然地从暴力求解的思路逐步过渡到更高效的优化方案设计，在真实编程实践中这一思维方式更能贴近实际情况并被广泛应用

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

CPU的GHz的含义

当前所有CPU的执行频率单位均为GHz。大致相当于每秒能够处理一亿条指令也就是每秒运行一亿次指令。然而不同型号的CPU之间存在一定的性能差异因此在分析算法复杂度时，默认这种简化假设是合理的。

算法题n的量级

根据CPU每秒可执行一亿次的计算能力进行估算，在题目设定下n的取值范围为 $10^5$ 时，则采用基于 $O(n^2)$ 时间复杂度的传统算法将导致运行时间超出一秒的限制条件。因此，在这种情况下使用具有 $O(n^2)$ 时间复杂度的算法会导致运行时间超出一秒的限制这一情况会被视为题目的核心要求之一。为了满足这一限制要求，则必须采用双指针、队栈或者动态规划等方法来进行优化处理。

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

n 的量级	时间复杂度	一般场景
四万或者五万	$O(n)$	双指针、动态规划、队栈
两万或三万	$O(nlog(n))$	排序、贪心
几千	$O(n^2)$	暴力
几十或者一两百	$O(

全部评论 (0)

还没有任何评论哟~