文章目录
一、复杂度理论
二、时间复杂度
1、P 与 NP 问题
2、O 表示的复杂度情况
3、时间复杂度取值规则
4、时间复杂度对比
一、复杂度理论
----
时间复杂度 : 描述一个算法执行的大概效率...; 面试重点考察 ; 面试时对时间复杂度都有指定的要求 , 蛮力算法一般都会挂掉 ;
空间复杂度 : 程序执行过程中 , 所耗费的额外空间 ; 面试考察较少 , 程序中使用的空间 , 看变量的定义就可以知道大概数量..., 实现了哈希算法 , 很难看懂 ;
思维复杂度 : 是否容易想得出 ; 算法的原理是否容易理解 ;
算法是否容易理解 ;
字符串查找 KMP 的算法就很难理解 , 即使把代码展示出来 , 将原理说明..., 也是很难理解的 ;
一般 蛮力算法 时间复杂度 很高 , 但是 编程复杂度 和 思维复杂度 很低 , 代码容易理解 ;
如果对 时间复杂度 要求很高 , 如必须达到
O(n)
或
O(n^...等 ;
2、O 表示的复杂度情况
O
表示算法在 最坏的情况下的时间复杂度 ;
一般情况下 , 算法的时间复杂度都以最坏情况的时间复杂度为准 ;
但是也有特例 , 快速排序的最坏情况下 , 时间复杂度是