数据结构（一）
这是卡尼慕的第n篇文章
所有程序员必不可少的基础就是数据结构与算法，这也是我们在未来面试中必不可少的考点和加分点。
为什么会有数据结构的出现？数据结构对我们的代码有什么意义吗？
有数据，和组织数据的数据结构，程序的行为逻辑才可以确定，程序才可能有实际意义。
对于不同语言来讲，数据结构其实就是组织数据的思想和方法，都是大同小异的。因此不用纠结于什么语言的数据结构，掌握了就好了。
基础概念
抽象数据类型
是数据结构的一种概念
更有利于描述这个世界，如：用树或者图画遗传族谱。
是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。
容器
容器是一种数据结构，存储具有相同类型的对象。不同容器内部的组织方式不同，标准模版库包括了最常用的一些容器如：list、set、multimap、map、queue、stack、vector等。
迭代器
是一种设计模式，遍历并选择序列中的对象。
迭代器(iterator)其实和STL息息相关，STL里所有的容器都有迭代器的概念。迭代器有只读或可写之分，也有随机或顺序之分。其实可以把迭代器理解成特别的指针，它具有指针基本的操作（解引用*，自加++，自减--，指向结构体成员->等操作）。
算法的效率
虽然计算机能快速的完成运算处理，但实际上，它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序，我们就需要考虑到算法的效率。 一般我们使用时间复杂度和空间复杂度来评估算法的效率高低。
时间复杂度
评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
空间复杂度
评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。
大O表示法
我们一般使用O(f(n))来体现算法的复杂度。
大O表示法O(f(n))中的f(n)的值可以为1、n、logn、n²等，因此我们可以将O(1)、O(n)、O(logn)、O(n²)分别可以称为常数阶、线性阶、对数阶和平方阶。
计算方法：
找出算法中的基本语句
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
计算基本语句的执行次数的数量级：
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
常数阶 先举了例子，如下所示。
int sum = 0,n = 100; //执行一次
sum = (1+n)*n/2; //执行一次
System.out.println (sum); //执行一次
上面算法的运行的次数的函数为f(n)=3，根据推导大O阶的规则1，我们需要将常数3改为1，则这个算法的时间复杂度为O(1)。如果sum = （1+n）*n/2这条语句再执行10遍，因为这与问题大小n的值并没有关系，所以这个算法的时间复杂度仍旧是O(1)，我们可以称之为常数阶。
线性阶 线性阶主要要分析循环结构的运行情况，如下所示。
for(int i=0;i<n;i++){
//时间复杂度为O(1)的算法...}
上面算法循环体中的代码执行了n次，因此时间复杂度为O(n)。
对数阶 接着看如下代码：
int number=1;while(number<n){
number=number*2}
可以看出上面的代码，随着number每次乘以2后，都会越来越接近n，当number不小于n时就会退出循环。假设循环的次数为X，则由2^x=n得出x=log₂n，因此得出这个算法的时间复杂度为O(logn)。
平方阶 下面的代码是循环嵌套：
for(int i=0;i<n;i++){
for(int j=0;j<n;i++){
//复杂度为O(1)的算法 ...
}
}
内层循环的时间复杂度在讲到线性阶时就已经得知是O(n)，现在经过外层循环n次，那么这段算法的时间复杂度则为O(n²)。
常用的时间复杂度按照耗费的时间从小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)
这一期介绍了一下最最最基本的知识，下期该来看看排序算法了！冒泡，快排，堆排序哈哈哈哈，他们之间有什么区别呢？