老狗啃骨头之数据结构-小说算法

  每每从购物公园那个东门出来，抬头，总是能看到平安金融中心，感受这座深圳最高大楼带来那种视觉上的压迫和心理上的震撼，高耸如云，巍峨耸立。人类文明对自然的改造在今天的科技加成下，甚至让我们很难想象在不远的明天，将会面临何种意想不到的体验。

  这一砖一瓦、钢筋水泥、玻璃管材…… 差不多就是我们之前啰嗦半天的数据结构，但是钢筋水泥们如何能如此壮观的拔地而起，耸入云霄？就必须要考量各种因素来一套设计：如何搭梁架柱，如何飞管走线，如何修幅饰边…… 还要考虑各种气候、地质、环境等各种，等等等等太多太多因素，这样做出一个最优方案，一套近乎完美的设计。这个设计，就是算法。

  算法，是利用可用资源，解决问题的方案。就像盖一座平安大厦，钢筋水泥有了，这是数据结构；设计方案拿出来了，这是算法；建筑工人叮咣叮咣机器设备开始轰鸣…..这是程序在运行了！
  我们再来回顾一下这个公式定义：

数据结构 + 算法 = 程序
  确实，很多事情抽丝剥茧，归纳总结抽象一下，差不多也是这样子的。
  在计算机里，我们讲数据结构的时候，计算机程序的这个算法，就是用计算机解决问题的方案。

  同样是盖大房子，古代欧洲人喜欢用石头，中国人喜欢用木头，现代人则几乎相当依赖钢筋水泥。不同的方案，导致了在实用性、功能性、艺术性上，各有千秋。算法也一样，达到同样的目的、解决同样的问题，方法可能有千般万种，那怎么来评判，计算机中算法的优劣呢？
  一般计算机算法的评判，会考虑两个维度：空间和时间。完成同样功能的前提下，运算过程占用空间越小、使用时间越少，是更好的算法。

空间复杂度

  在早期的计算机中，计算单元的体积是很大的，还需要足够庞大的电力来维持运行，从数据的结构上进行精简优化，利用更少的单位完成计算，是非常非常必要的；当然在今天科技水平加持下，芯片领域的摩尔定律进化早已让空间维度不再显得那么捉襟见肘，但在超大数据的运算过程中，相对复杂的数据结构是同样会导致性能下降，以至会产生瓶颈。当然，普通计算中，空间结构的复杂也会导致存读取用花费更多时间，只不过现在计算机性能足够好，我们感觉起来不是那么明显了。说这个在程序中的实际运用，一维数组能解决的，最好不要二维，二维能解决的，最好不要三维；线性表能搞定的，最好不要弄成树或者图，除非说复杂结构能换来算法在时间维度上绝对的优势。在研究算法的层面上，算法的空间复杂度，也是很重要很重要的。

时间复杂度

  时间这个维度，很好理解，就是一个算法，程序运行体现出来的时长，时间用得越少，效率就越高，我们说就是好的算法。
  在实际编程中，我们经常会去遍历一个结构，比较常见的是遍历线性结构，这个线性表长度为n，从头到尾来一遍，我们把这每次遍历组成元素的“时间”，看成1，那这个算法的时间复杂度就为n。
  写成代码，可以直观地看到：

for(int i = 0 ; i < n ; i++){
    // do;
}

  这段代码的时间复杂度，我们就可以认为是n。
  我们也会经常遇到很多遍历再遍历的情况，写成代码就是循环套循环，代码如下：

for(int i = 0 ; i < n ; i++){
    for(int j= 0 ; j < m; j++){
        // do;
    }
}

  这种n×m的，情况，我们把n和m看成是一样的，认为直接就是n2。
  在数据结构和算法里，我们对于这个时间复杂度，一般是这么记得：复杂度n，记为O(n)；复杂度n2，记为O(n2)。以此类推，根据对应的数学模型，我们总结出以下常见的时间复杂度时间关系：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)
  一般说，随着数据结构复杂度和解决问题的复杂度的增长，时间复杂度也是随之增长的。我们在研究算法时，一般考虑的是它的最差情况，实际使用时还要考虑数据结构和数据本身的特性，来衡量这个算法的优劣。

  在相同的资源条件下，空间复杂度和时间复杂度决定了一个算法的好坏，实际运用过程中，我们还是可能会遇到空间换时间、时间换空间的情况，实际运用，很多情况下是没有最优、只有最合适的，只有精于计算、深刻理解，才好做出最恰当的算法设计。