一、数据类型

定义：一组值的集合以及定义在这组值上的一系列操作。(值集 + 操作集合)

站在计算机和程序员的角度：计算机只认识 0 和 1 ，如果直接让程序员操作0和1，想必会疯掉一批人，所以，由编译器 和编程语言将他们抽象成基本数据类型供广大猿类使用。所以，通过编译器和编程语言来确定他们在计算机中的长度和可以进行的操作。

举例：例如Java中基本类型int占用2字节(16位)，而在变他们可以进行 " +，-，x，/“ 等操作，不可以进行并，交，差等操作。所以它的值集：-2^15 ~ 2^15-1(因为0的存在所以需要-1)，操作集合：” +，-，x，/ “ 等

分类：

• 基本数据类型
  系统定义的(编程语言提供的)数据类型成为基本数据类型，如Java中的int,float,double,char等。
• 用户自定义数据类型
  用户可以自己定义的数据类型，如Java中的类。

二、数据结构(有关系的数据 + 存在的关系)

定义：由相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。它是存储和组织数据的一种方式。(实质：有关系的数据元素 + 关系集合)

三要素：(数据关系 + 数据存储 + 数据操作)

• 数据的逻辑结构 ：反映数据元素之间的逻辑关系的数据结构,主要是指他们之间的前后关系，如集合关系(前后无关系，但同属一集合)，线性结构(前后一对一)，树形结构(前后一对多)，图形结构(前后多对多)。
• 数据的存储结构(物理结构)：数据的逻辑结构在计算机存储空间的存放形式，也就是数据在计算机内的表示。如顺序存储，链接存储，散列存储，索引存储等。一种数据结构可表示成一种或多种存储结构。
• 数据的运算结构：也就是这些数据可以进行哪些运算操作。

三、数据结构 VS 数据类型 VS 抽象数据类型

数据结构：抽象的数据对象以及该数据对象集合中的数据元素之间的相互关系。
从名字上来说，它表示的就是数据的结构，包括构成的成分，构成的方式和结构。
它反应的数据内部的构成方式，常用结构图来表示(如结点，边等)

数据类型：计算机程序中的数据对象以及定义在这个数据对象集合上的一组操作的总称。
从名字上看，它表示的是数据的类型，也就是将数据按照数据结构进行分类后，所属的类型。即同一类数据的所有称为一个数据类型。它最早出现在高级程序语言中，用户来刻画操作对象的特征，按照“值”的不同，可以分为非结构的原子数据类型和结构类型。
所以,一类数据结构对应着一种数据类型。

抽象数据类型ADT：一个数学模型以及定义在该模型上的一组操作。它与具体在计算机内部如何实现的无关，即只要它的数字特性不变，不管内部实现如何，它都不影响外部使用(类似面向对象的封装思想)。
抽象数据类型和数据类型实际上是一个概念，它可以理解为数据类型的进一步抽象，即将数据类型和数据类型上的运算捆绑在一起进行封装，这样我们可以自定义一些不同的数据结构，如：类结构等。只是原子类型已经由编程语言为使用者已经实现了而已。

四、算法

定义：指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

特征：

• 有穷性：执行步骤又穷
• 确切性：每一步都是确切的，不具备二义的；
• 输入输出：算法有0-n个输入和1-n个输出；
• 可行性：算法是可行的，不是凭空想象不切实际的。

衡量标准：评价一个算法的好坏的标准

• 时间上的衡量：使用最糟糕情况下的操作次数来衡量算法时间上的消耗：它比较的是算法的操作数，指出了算法运行时间的增速。，按增速由慢到快有：O(log n)，O(n)，O(n * log n)， O(n^2 )，O(n)。算法时间复杂度描述了，随着输入规模的增大，其运行时间以什么样的速度增加。通常算法时间分析可以从最好情况，平均情况，最坏情况考量(分别取决于不同的输入)，而且采用渐进曲线来替代问题规模n和算法的操作次数所对应的曲线，如：对于输入规模为n，操作次数为n^3 + n^2 + n + log(n)这样的算法，我们使用O(n^3)作其算法时间复杂度。
• 空间上的衡量：使用算法在运行时所使用的临时空间来衡量算法在空间上的消耗。
  以上衡量标准不考虑算法的运行环境(机器设备)，只是从算法(解决方案)的角度来分析，具有很强的针对性。

算法复杂度的分析

• 循环:迭代次数 x 循环体内语句执行时间(注意循环条件和循环体)

//循环执行n次
for(i = 1;i<=n;i++)
    m = m + 1;//常数时间c

时间为：c x n = cn =O(n)

• 嵌套循环：由内到外，所有循环规模的乘积

//外循环执行n次
for(i = 1;i<=n;i++)
    //内循环执行n次
    for(j = 1;i<=n;j++)
        m = m+1;//常数时间c

时间为：c x n x n = c x n^2 = O(n^2)

• 顺序执行语句：每条语句的运行时间之和

l = l+1;//常数时间c1
//循环执行n次
for(i = 1;i<=n;i++)
  t = t+1;//常数时间c2
//外循环执行n次
for(i = 1;i<=n;i++)
    //内循环执行n次
    for(j = 1;i<=n;j++)
        m = m+1;//常数时间c3

时间为：c1 + n x c2 + n x n x c3 = O(n^2)

• if-else：

//条件：常数c1
if(array.length() == 0)
    return false;//常数c2
else{
    //for循环n次(记array.length()为n)
    for(i = 1;i<=array.length();i++){
        if(array[i].equals(x))//条件执行常数c3
            return false;//常数c4
    }
}

时间为：c1 + c2 + (c3 + c4) x n = O(n)

• 对数时间复杂度:

//第k次循环时， 2 ^ k = n，即k = log(n)
for(j = 1;i<=n;i = i * 2)
        m = m+1;//常数时间c1

时间为：O(log(n))

• 递归问题解决
  • 分治主定理(未完)
  • 问题规模减小和递归求解主定理(未完)