002、算法复杂度

东方耀

002、算法复杂度
1、面试必考
2、算法是否高效 通过复杂度衡量
3、空间复杂度 时间复杂度 任何AI工程师必须深入理解的概念
4、算法设计的时候一定要考虑复杂度


复杂度理论  complexity Theory  P问题 NP NP hard等


O(N)  O(N^2)   :  o notation


O(N) 线性的复杂度  
时间复杂度：time complexity  需要多少次的操作
a+b  或 a *b 都是一次操作
空间复杂度：space complexity 需要多少个内存单元（用了多少个变量）


ipynb文件在附件，可供下载！


O(1) 常数的复杂度


Merge Sort 归并排序
大问题 拆分为 子问题   递归的过程
一般拆分为2个子问题 如果拆分为3个子问题根据主定理 严格推导
它们的时间复杂度是一样的


归并排序的时间复杂度计算：主定理 master theorem
结论：O( nlog(n) )


指数级的复杂度 O(p^n)  p为常数
多项式复杂度 O(n^p)  p为常数


例子：斐波那契数列
递归的时间复杂度 O(2^n)  指数级
递归的空间复杂度 上下文切换 stack栈 入栈出栈  O(n)


优化方法：斐波那契数的循环实现


O(1) < O(log n) < O(n) < O( n logn ) < O(n^2) < O(n^2 logn)  < O(n^3) < O(n!)  


P、NP、NP-Complete、NP-Hard问题
如果一个问题可以找到一个只有多项式复杂度的算法
（这个算法可以在多项式时间内求得解），那这个问题就属于P（Polynomial）问题（即多项式问题）
无法找到任何多项式复杂度算法的可解问题，则称为指数型（Exponential）问题
没有任何可解算法的问题，则称为不可解问题
多项式时间内是否可以验证一个解，如果可以，这个问题就被称为NP（Non-Deterministic Polynomial ）问题（即非决定性多项式问题）。


东方老师AI官网：http://www.ai111.vip
有任何问题可联系东方老师微信：dfy_88888
【微信二维码图片】