基本概念和术语
-
数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别并输入给计算机处理的符号集合。
-
数据元素：是组成数据的，具有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。
-
数据项：一个数据元素可以由若干个数据项组成，数据项是不可分割的最小单位，但是在实际的应用分析中，数据元素才是数据结构中建立数学模型的着眼点。
-
数据对象：是性质相同的数据元素的集合，是数据的子集。
数据.png
-
数据结构：是相互之间存在一种或者多种特定关系的数据元素的集合
逻辑结构与物理结构
- 逻辑结构：是指数据对象中数据元素之间的相互关系。
逻辑结构.png
- 物理结构：指数据的逻辑结构再计算机中的存储模式，有顺序存储和链式存储两种模式。
- 顺序存储结构：是把数据元素放在地址连续的存储单元中，其数据间的逻辑关系和物理关系是一致的。
- 链式存储结构：是把数据元素放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
抽象数据类型
数据类型：指一组性质相同的值的集合及定义在此集合上的一些操作的总称。而将这些数据的相同的性质给抽象提取出来就成为了抽象数据类型。
抽象数据类型 （Abstract Date Type， ADT）：是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅仅取决于它的逻辑特性，与其在计算机内部如何表现和实现无关。
- 算法定义： 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令都表示为一个或者多个操作。
- 算法特性 ：输入输出，有穷，确定，可行性。
- 算法设计的要求 ：正确性、可读性、健壮性、事件效率高和存储量低。
算法效率的估算方法
-
事后统计方法
定义：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
缺点：使用此方法必须先编好程序，此外运行时间和计算机的配置有很大关系，不利于不同算法的比较，而且效率的比较与样本的数量有很大关系，有些算法在样本数较少的情况下较优，但是在样本量较大的情况下却远劣于其他算法。 -
事前分析估算方法
定义：在计算机程序编制前，依照统计方法对算法进行估算。
程序在计算机上运行所消耗的时间由以下四个条件决定：
- 算法所采用的策略、方法
- 编译产生的代码质量
- 问题的输入规模
- 机器执行指令的速度
其中第一条是算法好坏的根本，第二条跟程序员的水平有关，也和语言的性能有关，第四条是和机器的配置有关。因此除去人为造成的影响和客观情况，一个算法的好坏是与算法本身的策略方法以及输入的数据大小由很大关系的。
用一个简单的例子来说明：
- 算法1
for (int i = 1; i < 100; i++) { //执行n+1次
sum = sum + i; //执行n次
}
System.out.println(sum); //执行1次
- 算法2
sum = (1 + n) * n /2; //执行1次
System.out.println(sum); //执行1次
如果对赋值循环条件和输出进行忽略的话，在只考虑循环过程的情况下，算法1总共执行了n次，而算法2执行了1次，很明显在得到同样的结果下算法2要比算法1好很多。
- 算法3
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
x++; //执行100 *100次
sum = sum + x;
}
}
System.out.println(sum); //执行1次
算法3在忽略赋值条件和输出的情况下执行了100*100次，即为n²次。
那为什么要忽略赋值条件和输出呢？
因为在不同水平的程序员以及使用不同的语言的情况下，赋值条件以及输出所需要执行的次数是不同的。而且通过经验得知，这些赋值输出的执行次数相比于基本操作是很少的。
因此，测定运行时间最可靠的方法是计算对运行时间有消耗的基本操作的执行次数。
算法的时间复杂度
定义：在进行算法分析的时候，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n) = O(f(n))。它表示随着问题规模的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
从定义上看可能有些复杂，我们可以这样理解，T（n）是算法复杂度的表现，而T（n）= O（f（n）），O函数是不变的，因此T（n）只与f（n）相关，而f（n）则是代表了问题规模n的增大，算法中需要的执行步数的变化函数。
下面我们看下推导大O阶的方法：
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中，只保留最高阶项
3.如果最高阶存在且不是1，则去除与这个项相乘的常数。
对于这个方法的理解如下：
因为我们在测试算法的时候，这些算法在实际运用中一般所输入的数据都是比较大的量，这样对算法优劣的比较才有意义。所以根据高数中的等价无穷大的比较原则，以上三个方法可以简化为只需考虑最高次项的次数，其他都不需要考虑。
以上三个案例的时间复杂度为：
- O（1）：常数阶
我们可以简单地把常数阶理解为，不管n是如何变化的，执行这个算法所需要的执行步数都是一个固定的值，为常数。 - O（n）：线性阶
线性阶可以理解为，随着n的变化，执行这个算法所需要的执行步数也呈线性变化。 - O（n²）：平方阶
平方阶则是随着n的变化，执行算法所需要的步数是n²的线性变化量。
注意：对于常数阶来说，不存在O（2）、O（3）这种形式。对于分支结构而言，因为不管何种条件，程序总要选择一种情况执行下去，所以可以把分支结构视为O（1）。
最坏情况与平均情况
在查找一个随机数字数组的某个数字的时候，运气好的话第一次就能够查找到，运气不好的话要找到最后才能够找到。所以，对于运气特别好的情况下，无论n为何值，时间复杂度都为O（1），运气不好的时候则为O（n）。而我们在编写程序的时候，要保证其不会出错，因此要考虑运气最不好的情况下的时间复杂度，也就是最坏情况。
而平均运行时间是所有情况中最有意义的，它也是期望的运行时间。但是在对算法的分析中，平均运行时间需要进行大量的数据验证才能够的出来。
在没有特殊说明的情况下，我们采用的都是最坏情况复杂度。
网友评论