算法复杂度分析：由于相同算法在不同测试环境,硬件设备上处理数据的效率并不相同,且不同算法的执行效率受数据规模的影响很大(如下图).所以在实际编码和进行算法优化时就需要有一个理论分析方向作为指导.算法复杂度分析使用大O复杂度分析法.

    时间复杂度的概念：执行的次数和同数量级（n最高次方数）取商是常数，那么同数量级就是这个算法的时间复杂度。其也叫时间渐进复杂度，并不表示准确的代码运行时间,而是表示代码执行时间随着数据规模增长的变化趋势。

    时间复杂度的计算过程：
    1. 算出每一行语句执行的次数
    2. 求和，推导出一个n的表达式T(n)
    3. 找出同数量级的表示式（n的最高次方）
    4. T(n)/同数量级–>常数，那么同数量级就是此算法的时间复杂度

       时间复杂度示例：

      【定义说明】--维基百科 

       在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 n0 大）的输入，它至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3).

    假设每一行代码 执行消耗cpu时间均为cpu_time, n表示数据规模,则以上三段代码逐行执行总时间为:

    TNN(n)=(1+n+2n2+1)*cpu_time

        TN(n)=(1+2n+1)*cpu_time

        T1(n)=(1)*cpu_time

    由上面表达式可以知道代码执行总时间 T(n) 与每行代码的执行次数 n 成正比,引入大 O 时间复杂度后,可以表示为:T(n)=O(f(n)),其中T(n)表示代码执行的时间;n 表示数据规模的大小;f(n)表示每行代码执行的次数总和.

    则代码执行时间TNN(n)=O(2n2+n+2);TN(n)=O(2n+2);T1(n)=O(1)

    当 n 很大时,而公式中的低阶项、常数项(无论是100,1000,10000,100000……)、系数三部分并不能对增长趋势造成很大的影响,所以都可以忽略。 则上述3段代码的时间复杂度，就可以记为:TNN(n) = O(n2);TN(n) = O(n);T1=O(1)。

     时间复杂度分析方法：

• 假设数据规模非常大

• 关注循环最多的那部分代码

• 总复杂度等于量级最大的那段代码的复杂度

• 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

   常见的时间复杂度：O(n)、O(1)、O(n)=n^2、O(n)=n^3、O(log₂n)、O(nlog₂n)，具体举例见博客：

https://blog.csdn.net/yan_jin_feng/article/details/98172281

https://www.cnblogs.com/diaosir/p/10407523.html

   注：时间复杂度对数阶的理解请看文末【参考】2。

   时间复杂度常用的记忆法：

   1）访问数组中的元素是常数时间操作，或说O(1)操作。

   2）一个算法如 果能在每个步骤去掉一半数据元素，如二分检索，通常它就取O(logn)时间。

   3）用strcmp比较两个具有n个字符的串需要O(n)时间。

   4）常规的矩阵乘算法是O(n^3)，因为算出每个元素都需要将n对元素相乘并加到一起，所有元素的个数n^2。

   5）指数时间算法通常来源于需要求出所有可能结果。例如，n个元素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。

   6）指数算法一般说来是太复杂了，除非n的值非常小，因为，在这个问题中增加一个元素就导致运行时间加倍。

   7）在计算时间复杂度时，我们一般使用的大O表示法，其时间复杂度，从小到大的排序是：

    (1) < (logn)< (n)< (nlogn)< (n^2)<…< (2^n)< (n!)

   空间复杂度的概念：也叫渐进空间复杂度，概念和时间复杂度类似，表示数据规模和存储空间的增长关系。  

     举例:

    上述代码第2行代码申请了容量为n的一个[]string 类型切片的存储空间，其他行代码申请的空间都是常量,所以空间复杂度为O(n)。

   四个算法复杂度的概念：  （参见【参考】-1）

   因为同一段代码，在不同输入的情况下，复杂度量级有可能是不一样,所以可以引入一下几种时间复杂度相关概念.

• 最好情况时间复杂度(best case timecomplexity)

  极端好的情况下算法时间复杂度

• 最坏情况时间复杂度(worst case timecomplexity)

  极端坏的情况下算法时间复杂度

• 平均情况时间复杂度(average case timecomplexity)

  随机情况下算法时间复杂度

• 均摊时间复杂度(amortized time complexity)

  存在时序规律的平均情况时间复杂度

【参考】

[1] 算法复杂度分析
[2] 算法时间复杂度-对数阶

      点滴分享，福泽你我！Add oil！