网站制作模板百度网盘,网站建设的具体流程,网站建设国外拂去其,齐齐哈尔建设网站【0】README
0.1#xff09; 本文总结于 数据结构与算法分析#xff1b;旨在了解 算法分析涉及到的数学基础、时间复杂度分析法则、和其它的一些法则 和 结论#xff1b; 【1】 数学基础
1.1#xff09;本书将使用以下4个定义#xff1a; 对上述定义的分析#xff0…【0】README
0.1 本文总结于 数据结构与算法分析旨在了解 算法分析涉及到的数学基础、时间复杂度分析法则、和其它的一些法则 和 结论 【1】 数学基础
1.1本书将使用以下4个定义 对上述定义的分析Analysis
A1第一个定义是说TN的增长率小于等于fN的增长率A2第二个定义是说TN的增长率大于等于gN的增长率A3第三个定义是说TN的增长率等于hN的增长率A4第四个定义是说TN的增长率小于pN的增长率 它不同于大O因为大O 包含增长率相同这种可能性
1.2我们引入了相对增长率的概念 并将其应用到算法分析 1.3比较1000N 与 N^2 的大小 虽然N 较小时1000N 大于 N^2 但 N^2 以更快的速度增长因为N^2 最终将更大 1.4这种情况下N1000 是个转折点 第一个定义说最后总会存在某个点 n0 从它以后 cf(N) 总是至少与 T(N)一样大 从而忽略掉常数因子 则f(N) 至少与 T(N) 一样大 1.5上界与下界 当我们说TNOfN时我们是在保证函数TN是在不快于fN的速度增长因此fN是TN的一个上界 也可以说fNΩTN意味着TN是fN的一个下界 1.6直观上说 1.7我们需要掌握的结论为 1.8以上信息足以按照增长率对大部分常见的函数进行分类如下图 对上图的分析Analysis
A1首先将常数或低阶项放进大O是非常坏的习惯不要写成TNO2N^2或TNO(N^2N) 这两种情况下正确的形式是 T(N)O(N^2)A2我们总能够通过计算极限 来确定两个函数 f(N) 和 g(N)的相对增长率必要的时候可以使用洛必达法则A3上述极限有4种可能情况 【2】 要分析的问题
2.1要分析的最重要的资源一般来说就是运行时间了 分别为输入为N时算法所花费的平均运行时间和最坏情况下的运行时间显然前者小于等于后者 2.2一般说来若无相反的指定则所需要的量是最坏情况下的运行时间
原因1它对所有的输入提供了一个界限包括特别坏的输入而平均情况分析不提供这样的界限原因2平均情况的界计算起来通常要困难得多 在某些情况下 平均的定义可能影响分析的结果 【3】 运行时间的计算
3.1 一个简单的例子 对以上程序进行时间分析Analysis
A1 line 5 占用一个时间单元 line8 占用一个时间单元A2 line7 每执行一次占用4个时间单元2次乘法1次加法1次赋值 而执行N 次共占用4N 个时间单元A3 line6 在初始化i、测试 iN 和对 i 的自增运算中隐含着开销所有这些总开销是初始化 1个时间单元、所有的测试N1 个时间单元、以及所有的自增运算N 个时间单元共2N 2A4 所以我们忽略调用函数 和 返回值的开销得到总量是 6N4 2 4N 2N 2 我们可以说该函数是 ON 也即是说 6N4的增长率 小于等于 N的增长率确切的说是等于
3.2 一般法则
if(condition)S1
elseS2 对于递归的看法 当一个递归可以被转化为循环时其递归使用效率低得离谱当然也就是说当递归被正常使用时将其转换为一个简单的循环结构是相当困难的
