开篇

你也许已经发现了，工作了几年，原以为已经是一只老鸟。但看到刚参加工作的同事，你发现，原来自己一直在原地踏步。跟新人相比，你的唯一优势就是对业务更熟悉而已，别的就没有什么优势了。

怎样才能够让自己更上一层楼呢？学习更多的框架？做更多项目？其实，程序员真正要做的是修炼内功，也就是夯实基础。比如设计模式、网络原理，当然也包括接下来要说的数据结构与算法分析。

一、为什么要学习数据结构与算法分析

1. 告别烂代码，写出性能更好地代码。
2. 解决问题的思路和方法，编程之外也有应用。
3. 思考能力才是程序员的核心竞争力，而算法能够有效地锻炼这方面。

当然也有其他原因，进大厂、不被淘汰、完成领导对代码简洁度性能的要求。

二、如何学好

1. 边学边练，一周用2~3个小时刷题。
2. 带着疑问去学习，多想为什么。
3. 学习算法是个需要沉淀的过程，切勿急于求成。

三、复杂度分析

复杂度分析是算法学习的精髓，几乎贯穿整个学习过程。掌握了复杂度分析，恭喜你，数据结构与算法分析的学习已经完成了一半。

• 时间复杂度

大O时间复杂度实际并不是代码的真正执行时间，而是代码执行时间随数据规模增长而呈现的变化趋势。程序真正执行时间受环境以及数据规模影响很大，例如相同条件下i7处理速度肯定比i5快，i7处理器处理10条数据肯定比10W条块。
常见的空间复杂度就是 常量阶O(1)、线性阶O(n)、指数阶、对数阶O(logn)、线性对数阶O(nlogn)，指数阶。

funtion sum (int n) {   
    int sum = 0;    
    for (int i=1; i <= n; i++) {    
        sum = sum + i;  
    }   
    return sum; 
}
# 第 2 行代码执行了一次，第 3 、4各执行了 n 遍。所以时间复杂度为 2n + 1 , 也就是 n 。

1. 最好时间复杂度
2. 最坏时间复杂度
3. 均摊时间复杂度

   funtion find ( int[] array ,  int n ,  int m ) { 
   int position = -1;  
   for (; i < n; ++i) { 
       if (array[i] == m) {       
           position = i;       
           break;  
       }  
   }
   return position;
   }
   #如上代码，寻找m在数组中的位置。如果第一个元素就是 m 时间复杂度就是 1 。如果 m 不在数组中，时间复杂度就是 n 。这是就用到最好时间复杂度、最坏时间复杂度和平均时间复杂度。
   #最好情况，第一个元素就是m。所以，最好时间复杂度就是 1 。
   #最坏情况，m 不在数组中。所以，最好时间复杂度就是 n 。
   #均摊时间复杂度，此时共有 n + 1 可能性。每种情况累加后再除 n + 1，就是均摊时间复杂度。（ 1 + 2 + 3 ..... n + n ） / ( n + 1 ) = n ( n + 3 ) / 2 ( n + 1 ) ，简化后就是 n 。

• 空间复杂度

空间复杂度表示的是存储空间与数据规模之间的增长关系。

funtion getArray ( int n) {
    int i = 0;  
    int[] a = new int[n];
    for (  ; i <n; ++i) {  
        a[i] = i;  
    }
    return a;
}
#第 2 行代码申请了变量 a ，别处就没有再申请存储了。所以，空间复杂度就是 n 。

今日笔记主要内容是时间复杂度，只列举了简单的例子。

网上有很多题，建议大家去做下，熟能生巧是很有道理的。

以上内容，如有错误点或改进点，希望大家能够指出。有什么问题，也可以留言，大家一起讨论、学习，一起进步。