一、复杂度理论

时间复杂度 : 描述一个算法执行的大概效率 ; 面试重点考察 ; 面试时对时间复杂度都有指定的要求 , 蛮力算法一般都会挂掉 ;

空间复杂度 : 程序执行过程中 , 所耗费的额外空间 ; 面试考察较少 , 程序中使用的空间 , 看变量的定义就可以知道大概数量 ;

编程复杂度 : 代码可读性是否高 , 是否容易看懂 ; 写代码时的难度不高 , 别人读代码时的难度也不高 ; 如果写的时候经过长时间斟酌 , 那么可读性估计会很差 ;

如 : 字符串查找 ,

使用 蛮力算法 , 编程复杂度很低 , 很容易看懂 , 但是其时间复杂度是 O ( m × n ) O(m \times n)O(m×n) ;

如果使用 Rabin-Karp 算法 , 时间复杂度是 O ( m + n ) O(m + n)O(m+n) , 但是编程复杂度很高 , 实现了哈希算法 , 很难看懂 ;

思维复杂度 : 是否容易想得出 ; 算法的原理是否容易理解 ;

算法是否容易理解 ;

字符串查找 KMP 的算法就很难理解 , 即使把代码展示出来 , 将原理说明 , 也是很难理解的 ;

一般 蛮力算法 时间复杂度 很高 , 但是 编程复杂度 和 思维复杂度 很低 , 代码容易理解 ;

如果对 时间复杂度 要求很高 , 如必须达到O(n) 或 O(n^2)要求 , 则必须使用复杂的算法 , 双指针 , 动态规划 , KMP 等 , 代码会写几百行 , 很难理解 ;

二者之间需要综合考虑 , 相互作出一些妥协 ;

二、时间复杂度

1、P 与 NP 问题

P 问题 ( Polynomial ) , 是有效算法的集合 , 都可以在多项式时间内完成计算 , 其 时间复杂度都是多项式 ,

时间复杂度都是  O(n) ,  O(n^2)，O(n^3), O ( m + n ), O ( 1 ) , O ( n ) O(\sqrt{n}) O ( log ⁡ n ) O(nlogn) 等多项式 ;

n 一般都在底数的位置 , 不在幂次方的位置 ;

NP 问题 ( Nondeterministic Polynomial ) , 是没有找到一个算法可以在多项式时间内解决该问题 , 目前只找到了非多项式时间的解法 , 不确定该问题是否有多项式时间解法 ;

时间复杂度一般是 O(2^n)O(n^n) O ( n ! )  等 ;

2、O 表示的复杂度情况

O  表示算法在 最坏的情况下的时间复杂度 ;

一般情况下 , 算法的时间复杂度都以最坏情况的时间复杂度为准 ;

但是也有特例 , 快速排序的最坏情况下 , 时间复杂度是  O(n^2), 这个时间复杂度几乎不会遇到 , 一般情况下描述快速排序的时间复杂度时 , 使用 平均时间复杂度O(nlogn) ;

3、时间复杂度取值规则

只考虑最高次项 : 时间复杂度描述中 , 一般只考虑最高次项 ;

如 :

不考虑常数项 : 时间复杂度描述中 , 不考虑常数项 ;

不考虑系数项 : 时间复杂度描述中 , 不考虑系数项 ;

因此 , 对数的复杂度只有 O ( log ⁡ n ) O(\log n)O(logn) , 没有其它的底数或 n nn 次幂的情况 , 这些都可以提取成系数 ;

但是系数为 n nn 除外 ;

4、时间复杂度对比

O ( m + n ) 与 O ( m a x ( m , n ) ) 哪个复杂度更高 ;

n + m > m a x ( m , n ) > （m + n ）/2 

m a x ( m , n ) 是介于两个值之间的数值 ;

O ( n + m ) = O ( （m + n）/ 2 ) ，因此 O ( n + m ) = O ( （m + n ）/2 ) = O ( m a x ( m , n ) ) 

————————————————

本文转载自CSDN博主：韩曙亮

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-NC-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/shulianghan/article/details/119011214

一、复杂度理论

时间复杂度 : 描述一个算法执行的大概效率 ; 面试重点考察 ; 面试时对时间复杂度都有指定的要求 , 蛮力算法一般都会挂掉 ;

空间复杂度 : 程序执行过程中 , 所耗费的额外空间 ; 面试考察较少 , 程序中使用的空间 , 看变量的定义就可以知道大概数量 ;

编程复杂度 : 代码可读性是否高 , 是否容易看懂 ; 写代码时的难度不高 , 别人读代码时的难度也不高 ; 如果写的时候经过长时间斟酌 , 那么可读性估计会很差 ;

如 : 字符串查找 ,

使用 蛮力算法 , 编程复杂度很低 , 很容易看懂 , 但是其时间复杂度是 O ( m × n ) O(m \times n)O(m×n) ;

如果使用 Rabin-Karp 算法 , 时间复杂度是 O ( m + n ) O(m + n)O(m+n) , 但是编程复杂度很高 , 实现了哈希算法 , 很难看懂 ;

思维复杂度 : 是否容易想得出 ; 算法的原理是否容易理解 ;

算法是否容易理解 ;

字符串查找 KMP 的算法就很难理解 , 即使把代码展示出来 , 将原理说明 , 也是很难理解的 ;

一般 蛮力算法 时间复杂度 很高 , 但是 编程复杂度 和 思维复杂度 很低 , 代码容易理解 ;

如果对 时间复杂度 要求很高 , 如必须达到O(n) 或 O(n^2)要求 , 则必须使用复杂的算法 , 双指针 , 动态规划 , KMP 等 , 代码会写几百行 , 很难理解 ;

二者之间需要综合考虑 , 相互作出一些妥协 ;

二、时间复杂度

1、P 与 NP 问题

P 问题 ( Polynomial ) , 是有效算法的集合 , 都可以在多项式时间内完成计算 , 其 时间复杂度都是多项式 ,

时间复杂度都是  O(n) ,  O(n^2)，O(n^3), O ( m + n ), O ( 1 ) , O ( n ) O(\sqrt{n}) O ( log ⁡ n ) O(nlogn) 等多项式 ;

n 一般都在底数的位置 , 不在幂次方的位置 ;

NP 问题 ( Nondeterministic Polynomial ) , 是没有找到一个算法可以在多项式时间内解决该问题 , 目前只找到了非多项式时间的解法 , 不确定该问题是否有多项式时间解法 ;

时间复杂度一般是 O(2^n)O(n^n) O ( n ! )  等 ;

2、O 表示的复杂度情况

O  表示算法在 最坏的情况下的时间复杂度 ;

一般情况下 , 算法的时间复杂度都以最坏情况的时间复杂度为准 ;

但是也有特例 , 快速排序的最坏情况下 , 时间复杂度是  O(n^2), 这个时间复杂度几乎不会遇到 , 一般情况下描述快速排序的时间复杂度时 , 使用 平均时间复杂度O(nlogn) ;

3、时间复杂度取值规则

只考虑最高次项 : 时间复杂度描述中 , 一般只考虑最高次项 ;

如 :

不考虑常数项 : 时间复杂度描述中 , 不考虑常数项 ;

不考虑系数项 : 时间复杂度描述中 , 不考虑系数项 ;

因此 , 对数的复杂度只有 O ( log ⁡ n ) O(\log n)O(logn) , 没有其它的底数或 n nn 次幂的情况 , 这些都可以提取成系数 ;

但是系数为 n nn 除外 ;

4、时间复杂度对比

O ( m + n ) 与 O ( m a x ( m , n ) ) 哪个复杂度更高 ;

n + m > m a x ( m , n ) > （m + n ）/2 

m a x ( m , n ) 是介于两个值之间的数值 ;

O ( n + m ) = O ( （m + n）/ 2 ) ，因此 O ( n + m ) = O ( （m + n ）/2 ) = O ( m a x ( m , n ) ) 

————————————————

本文转载自CSDN博主：韩曙亮

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-NC-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/shulianghan/article/details/119011214