文章目录
一、复杂度理论
二、时间复杂度
1、P 与 NP 问题
2、O 表示的复杂度情况
3、时间复杂度取值规则
4、时间复杂度对比
一、复杂度理论
----
时间复杂度 : 描述一个算法执行的大概效率...使用 蛮力算法 , 编程复杂度很低 , 很容易看懂 , 但是其时间复杂度是
O(m \times n)
;
如果使用 Rabin-Karp 算法 , 时间复杂度是
O(m + n)
, 但是编程复杂度很高..., 也是很难理解的 ;
一般 蛮力算法 时间复杂度 很高 , 但是 编程复杂度 和 思维复杂度 很低 , 代码容易理解 ;
如果对 时间复杂度 要求很高 , 如必须达到
O(n)
或
O(n^...与 NP 问题
P 问题 ( Polynomial ) , 是有效算法的集合 , 都可以在多项式时间内完成计算 , 其 时间复杂度都是多项式 ,
时间复杂度都是
O(n)
,
O(n^2)
,...等 ;
2、O 表示的复杂度情况
O
表示算法在 最坏的情况下的时间复杂度 ;
一般情况下 , 算法的时间复杂度都以最坏情况的时间复杂度为准 ;
但是也有特例 , 快速排序的最坏情况下 , 时间复杂度是