数据结构与算法——商院视角看“复杂度分析”

博主也是第一次当博主，想要做一名名副其实的程序员，当然本质可能还是个商科生，看到博客的朋友可以一起交流经验，wechat：LYI_1998

一、明确两个问题

1、算法为何进行复杂度分析？

一个算法消耗时间控件不可预先算出，需运行后才知结果。那么面对较为复杂的算法，采取不同的方法，在理论上预测，进而对最优方法进行预测选择就必不可少。两种方法分为：事后统计法和事前分析估算法。
然而，前者受两因素影响：一为测试环境，二为数据规模。后者虽存在估算不精准缺点，但更具有普适性。

对算法进行预测分析包括以下方面：

（1）预测算法所需的资源

        《1》计算时间（CPU消耗）

        《2》内存空间（RAM消耗）

        《3》通信时间（带宽消耗）

（2）预测算法的运行时间

          在输入规模一定时，所执行的基本
          操作的总数量，即算法的时间复杂度。

2、如何衡量算法复杂度？

算法分析目的依旧是选择与改进算法，故对一个算法的评价主要从时间复杂度和空间复杂度考虑！

二、复杂度基本概念

1、时间复杂度

1.1 基本概念

含义：时间复杂度，通俗的讲，就是算法运行时间，学术上讲，是一个关于代表算法输入值的字符串的长度的函数。
表示：用大O表示，注意，其中不包含低阶项和首项系数。是渐进的，即考察当输入值大小趋近于无穷的时的情况，记作O(f(n))。
PS：全称为渐进时间复杂度，即算法执行时间和数据规模之间的增长关系。
四个概念：最好情况时间复杂度；最坏情况复杂度；平均情况复杂度；均摊时间复杂复。

1.2 求解时间复杂度步骤

（1）找执行次数最多语句
（2）计算该语句的最高数量级，其他省略
（3）大O表示其时间复杂度

1.3 法则

（1）加法法则：总复杂度等于量级最大的那段代码的复杂度
（2）乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
（3）求和法则：T1(m) + T2(n) = O(f(m)) + g(n))
（4）求积法则：T1(m) * T2(n) = O(f(m) * f(n)),和乘法法则一致

1.4 复杂度量级举例

非多项式量级：指数阶【O(2的n次方)】，阶乘阶【O(n!)】，一般无效
多项式量级：常数阶、对数阶、线性阶、线性对数阶、平方阶等，有效
PS：对数阶应该注意一下：

2、空间复杂度

含义：渐进空间复杂度，即表示算法的存储空间与数据规模之间的增长关系，也是问题规模为n的函数，分析过程和时间复杂度类似
所占空间常分为：算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间以及算法在运行过程中临时占用的空间
常见空间复杂度：O(1)、O(n)、 O(n²)

三、所谓的商院视角

PS：水平有限，随便水水
其实在数据规模越大的情况下，算法不同规格的时间复杂度的渐进化影响越来越大，商业调控中的因素也是这样，在规模尚小时，细微因素对产品的影响并不大，但当产品规模越来越大时，整个的系统的架构需要重建，此时就相当于算法的优化！所以最好是事先选择好合适的算法，才不会出现推倒重来的不必要情况的发生！
———————————————————————
参考以及建议阅读：
1.复杂度分析