算法及时空复杂度思维脑图思维导图
算法的概念，特性以及重要指标内容讲解
树图思维导图提供 算法及时空复杂度思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 算法及时空复杂度思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：8de38bf114fe1c6450f67e1acc502f90
思维导图大纲
算法基本概念思维导图模板大纲
什么是算法
程序=数据结构+算法
算法对特定问题求解步骤的描述
五大特性
有穷性
确定性
可行性
有0个或多个输入
有1个或多个输出
好的算法
正确性：正确解决问题
可读性（readability）
健壮性（鲁棒性，robustness）：处理异常
高效率低存储需求
两个重要指标
（渐进）时间复杂度
概念
算法输入规模的函数
三种复杂度
最好时间复杂度
最坏时间复杂度
平均时间复杂度
表示法
O表示法：渐进上界
如果存在正常数c和n0使得当N ≥ n0 时，T(N) ≤ cf(N)，则记为T(N) = O(f(N));
Ω表示法：渐进下界
如果存在正常数c和n0使得当N ≥ n0 时，T(N) ≥ cg(N)，则记为T(N) = Ω(g(N));
例：f(n) = 10n^2 + 4n + 2≥10n^2，所以，f(n) =Ω(n^2)。
θ表示法：定义了一个精确的渐进
当且仅当T(N) = O(h(N))且T(N) = Ω(h(N));
例f(n) = 10n^2 + 4n + 2 = θ(n^2)
o表示法
O表示法去掉=而已
计算方法
频度
基本操作的原操作，即执行次数最多的一个操作重复执行的次数
设循环次数t，判断循环何时＞n，解出t和n的关系
设循环中与T(n)成正比的变量为t
外层变量是内层的条件：写求和公式
外层m次，内层n次：T=O(M*N)
求和非线性运算，设外层k次，求内层f(k)次，由外层的g(k)<n<g(k+1)，求f(k)与n有关范围
时空权衡原则
通过降低或提高算法的空间效率来提高或降低时间效率以解决问题的方法。
性能推导问题
如果遇到性能推导问题，一般来说O(kn) = kO(n)，其中k为常数
空间复杂度
计算方法
分析所占空间x与问题规模n的关系，x的数量级O(x)即为空间复杂度
一般来说递归程序空间复杂度=递归调用深度
若递归每次都建立一个额外空间则额外分析
相关思维导图模板
树图思维导图提供 广播电视奖项及评奖标准 在线思维导图免费制作，点击“编辑”按钮，可对 广播电视奖项及评奖标准 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：a4210651fa3a78355ac9f5101bb2c616
树图思维导图提供 中国邮政运营重点指标提示 在线思维导图免费制作，点击“编辑”按钮，可对 中国邮政运营重点指标提示 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：549bb5cd0fb673b56a2dd461adc52fbd
沪公网安备 31011502019485号
上海工商