东方耀AI技术分享

标题: 002、算法复杂度 [打印本页]

作者: 东方耀 时间: 2019-10-5 09:38
标题: 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
【微信二维码图片】

欢迎光临东方耀AI技术分享 (http://www.ai111.vip/)