数据结构和算法_数据结构求和

一、数据结构
1.什么是数据？
是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。 （数据不仅仅包括整型、实型等数据类型，还包括字符及声音、图像、视频等非数值类型）
数据 = 符号 这些符号需具备的两个前提：
① 可以输入到计算机中 （对于整型、实型等数值类型，可以进行数值计算）
② 能被计算机程序处理 （对于字符数据类型，需要进行非数值的处理。eg：视频、图片、音频等都是可以通过编码的手段变成字符数据来处理的。）

2．什么是数据元素？
是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理。也被称作记录。
一个数据元素可以由多个数据项组成。

3.数据项
数据项是数据不可分割的最小单位。

4.数据对象
是性质相同的数据元素的集合，是数据的子集。
（性质相同：这里指具有相同数量和类型的数据项，比如：人都有姓名、生日、性别等相同的数据项。）

5.数据结构
在现实世界中，不同数据元素之间不是互相独立的，而是存在着特定的关系，我们把这种关系称为结构。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系，也就是数据的组织形式。

二、算法

1. 最简单的求和问题：
例如：1+2+3+…+100 代码如下：
int result = 0; // 定义一个变量来储存运行后的结果
for(int i = 1; i<=100 ; i++ )
{
result += i; // 从1开始循环加到100
}
System.out.println(result); // 打印result的结果

2. 算法的定义
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。注意：算法不是唯一的，即同一个问题，可以有多种解决问题的方法。

3. 算法的特征
① 输入输出：算法可以有零个或多个输入，但至少有一个或多个输出。
② 有穷性：指算法在执行有限的步骤后会自动结束，不会无限循环，并且每一个步骤会在可接受的时间内完成。
③ 确定性：算法的每一步骤都有确定的含义。 即算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。
④ 可行性：算法的每一步都必须是可行的，即 每一步都能通过执行有限次数完成。

4.算法设计的要求
a.正确性：指算法至少应该具有输入、输出和加工处理无歧义性、能正确反应问题的需求、能够得到问题的正确答案。
判断一个算法是否正确的标准：算法程序对于非法的输入数据能够得出满足规格说明的结果。
b.可读性：算法设计的另一个目的是便于阅读、理解、交流。
c. 健壮性：当输入数据不合法时，算法也能够做出相关处理，而不是产生异常或什么莫名其妙的结果。eg：输入的时间、距离等单位不应该是负值。
d. 时间效率高 & 存储量低。
时间效率指算法的执行时间，即对于同一个问题，如果有多种算法能解决，那么用时最短的算法效率最高。
存储量指算法在执行过程中需要的最大存储空间，主要指算法程序运行时占用的内存或者外部硬盘存储空间。
5. 算法时间复杂度
如何推导一个算法的时间复杂度（即如何推导大O阶）？
第一步：用常数1取代运行时间中所有加法常数；
第二步：在修改后的运行次数函数中，只保留最高阶段；
第三步：如果最高阶段存在且不是1，则去除与这个项相乘的常数。
以上得到的结果就是大O阶。
eg：（1）常数阶
首先顺序结构的时间复杂度，例如以下算法：
int sum = 0, n = 100; /执行一次/
sum = (1+n)*n/2; /执行一次/
printf(“%d”,sum); /执行一次/

这个求和算法（高斯算法）的运行次数为：f(n)=3。

在这里，无论n等于多少，该算法的执行次数只有3次和12次执行差异之分，并且它的时间复杂度都为O(1)。
这种问题的大小与n（n的多少）无关的，执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。

常用的时间复杂度所耗费的时间从小到大依次：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

6. 算法空间复杂度
在写代码时，可以用空间换取时间。例如：
判断某一年是否为闰年？
方法1：通过写一个算法来判断，但是每给一个年份，都要通过一次计算才能得到结果。

方法2：通过建立一个有2050个元素的数组，然后把所有的年份按下标数字对应，如果这个年份是闰年，此数组项的值为1，不是则为0。 这样，判断某个年份是否为闰年的问题，就变成了查找这个数组某一项的值为1还是0的问题。此时运算是最小化，但要在硬盘或内存中需要存储这2050个1或者0。

算法的空间复杂度通过计算算法所需要的存储空间实现，算法空间复杂度的计算公式：
S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。