程序=数据结构+算法

一、数据结构

1、数据们之间的关系— —逻辑关系

是指数据元素之间的相互关系，是我们想象出来的，并没有实质性的将其存储在计算机中

线性结构：线性结构中的数据元素之间是一对一的关系

树形结构：树形结构中的数据元素之间存在一种一对多的层次关系

图形结构：图形结构的数据元素是多对多的关系

2、关系在计算机上的存储— —物理结构

是指数据的逻辑结构在计算机中的具体存储形式
顺序存储结构：开辟一组连续的空间存储数据通常用数组来实现，数组中空间本身是连续的，保证了数据之间的关系

链式存储结构：开辟一组随机的空间存储数据通常用节点来实现，节点不仅要存储数据还要存储下一个节点的位置以保证数据之间的关系

结合1、2

线性结构的物理存储方式：线性结构的顺序存储方式，线性结构的链式存储方式

树形结构的物理存储方式：树形结构的顺序存储方式，树形结构的链式存储方式

图形结构的物理存储方式：图形结构的顺序存储方式（邻接矩阵），图形结构的链式存储方式（邻接表）

二、算法

1、什么是算法

是解决特定问题， 求解步骤的描述

分析问题，一步一步求解，并得到结果 这一系列的步骤就称之为算法

同一个问题，可以有多种不同的解决方案，也就是说可以用不同的算法去解决同一个问题

2、如何评价算法的好坏

设计算法要提高程序运行的效率，这里效率大都指算法的执行时间

如何去度量一个算法的执行时间呢？

1）事后统计法

这种方法主要是通过设计好的程序和数据，利用计算机计时器对不同算法程序的运行时间进行比较，从而确定算法效率的高低。

弊端：

必须事先编好程序，再进行运行，如果程序处理的数据量较大，则会花费大量的时间和精力

时间的比较主要依赖于计算机硬件和软件环境

算法的测试数据设计困难，在数据量较小的时候，不管什么算法其运行时间都是很微小的，相差几乎为零。如果数据量大了，算法的优越性就出来了，但是这样又会耗费时间。
 

2）事前分析法
这种方法主要在计算机程序编制前，依据统计方法对算法进行估算。

一个高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

算法采用的策略、方法

编译产生的代码质量

问题的输入规模

机器执行指令的速度

第1条当然是算法好坏的根本，第2条取决于具体的编程语言，第4条取决于硬件性能

3、算法时间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度。简称时间复杂度。其中f(n)是问题规模n的某个函数
算法时间复杂度主要探究的是问题输入规模N的数量级不是算法的具体执行次数

1）、常数阶O(1)
就是那些无循环、无递归、与问题输入规模N无关的、逐行执行的代码。
int a = 1;

 int b = 2;

int c = 3;

int d = 4;

int e = 5;

System.out.println(a);

System.out.println(b);

System.out.println(c);

System.out.println(d);

System.out.println(e);

2）、线性阶O(n)
与问题输入规模有关的，主要是一层循环的代码，多个一层循环可以并列但不能包含。
int N = 10;

for (int i = 1; i <= N; i++) {

 System.out.println(i);

}for (int i = 1; i <= N; i++) {   

System.out.println(i);}
 

3）、线性阶O(n+m)
和线性阶O(n)一样，只不过我们有两种数据的输入规模
int N = 10;

int M = 20;

for (int i = 1; i <= N; i++) {    

System.out.println(i);

}for (int i = 1; i <= M; i++) {    

System.out.println(i);}

4）、平方阶O(n2)
与问题输入规模有关的，主要是二层嵌套循环的代码。
int N = 10;

for (int i = 1; i <= N; i++) {   

 for (int j = 1; j <= N; j++) {        

System.out.println(i + j);    }}

5）、平方阶O(nm)

和平方阶O(n2)一样，只不过我们有两种数据输入规模

int N = 10;

int M = 20;

for (int i = 1; i <= N; i++) {    

for (int j = 1; j <= M; j++) {        

System.out.println(i + j);    }}

6）、对数阶O(logn)
int key = 8;

int min_index = 0;

int max_index = arr.length - 1;

int mid_index = (min_index + max_index) / 2;

while (arr[mid_index] != key) {    

if (key < arr[mid_index])         

max_index = mid_index - 1;   

 if (arr[mid_index] < key) {        

min_index = mid_index + 1;   

 if (min_index > max_index) {        

mid_index = -1;        

break;    }    

mid_index = (min_index + max_index) / 2;}