数据结构与算法day1--了解数据结构与算法

程序 = 数据结构 + 算法

数据结构的主要学习内容：

• 数据之间的关系，将离散的数据规整化一
• 如果将这个关系具体实现并储存到计算中
• 基于关系之上对数据的具体操作，增删改查等
• 数据结构的具体使用场景

什么是数据结构：

数据结构的基本概念和术语：

• 数据
  • 数据是描述客观事实的符号，是计算机可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、浮点型等、还包括声音、图像、和视频等非数值类型。
• 数据元素
  • 数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被作为记录。比如，畜类的数据元素有牛、马、即猪....等动物都是畜类的数据元素
• 数据项
  • 一个数据元素可以由若干个数据项组成。比如：牛这样的数据元素的数据项可以有：牛角、腿、鼻子、嘴、耳朵等等。
  • 数据项是数据不可分割的最小单位
• 数据对象
  • 数据对象是性质相同的数据元素组成的集合，是数据的子集。
    • 性质相同：指数据元素具有相同数量和类型的数据项。比如，所有的畜类都有鼻子、耳朵、嘴等相同的数据项。
    • 数据的子集：在实际应用中，处理的数据元素通常具有相同性质，在不产生混淆的情况下，我们都将数据对象简称为数据。
• 数据结构
  • 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在计算机中，不同的数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。

数据结构的逻辑结构与物理结构

数据之间的关系—逻辑结构

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

• 线性结构：线性结构中数据元素之间是一对一的关系
• 树形结构：数据元素间是一对多的关系
• 图形结构：数据元素之间是多对多的关系

                      线性结构                                    树形结构                                        图形结构

关系在计算机上的储存--物理结构

是指数据的逻辑结构在计算机上的具体储存形式

• 顺序存储结构：开辟一组连续的空间存储数据，通常用数组来实现的，数组中空间本身是连续的，保证了数据之间的关系
• 链式存储结构：开辟一组随机的空间存储数据，通常用节点来实现，节点不仅要存储数据还要存储下一个节点的位置以保证数据之间的关系。

                                ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​                ​​​​​​​​​​​​​​        

                            

                      顺序存储结构                                                                        链式存储结构

         线性结构的链式存储方式中，通常左边存储的数据，右边存储的下一个数据的地址。

         树形结构的链式存储结构与线性结构的链式结构唯一不同的是：树形结构的式存储结构的节点又三部分组成，除了储存数据的部分外，左右两边都有储存下一个数据地址的部分。

什么是算法

算法的定义：

        算法是解决特定问题求解步骤的描述。分析问题，一步步求解，并得不到结构，这一系列的步骤就称之为算法
 

两种算法的比较

1~100求和问题

        大多数人可能会马上使用循环写出下面的代码：

//方案一
public class sum {
	public static void main(String[] args) {
		int s = 0;
        int N = 100;
		for (int i = 1; i <= N; i++) {
			s += i; 
		}
		System.out.println(s);
	}
 
}

        这是最简单的计算机程序之一，它就是一种算法。但这种算法是不是最高效的呢？

下面我们用另一种算法

回想一下我们在初中所学的，初中的时候，你会怎样求1~100的和呢？是不是脑子里立刻就会想起等差数列求和公式。那我们能不能将这个公式运用程序里面呢？

代码如下：
 

//方案二
public class sum {
	public static void main(String[] args) {
		int N = 100;
		int sum = (N + 1) * N /2;
		System.out.println(sum);
	}
 
}

上面两个代码，很显然方案二更高效。方案一随着N的增大，循环的次数也会增大，也就意味着执行的次数随着N的增大而增大

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

事后统计法

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

• 弊端
  • 必须事先编好程序，再进行运行，如果程序处理的数据量较大，则会花费大量的时间和精力
  • 时间的比较主要依赖于计算机硬件和软件环境
  • 算法的测试数据设计困难，在数据量较小的时候，不管什么算法其运行时间都是很微小的，相差几乎为零。如果数据量大了，算法的优越性就出来了，但是这样又会耗费时间。

事前分析法：

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

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

• 算法采用的策略、方法
• 编译产生的代码质量
• 问题的输入规模
• 机器执行指令的速度

算法时间复杂度

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

算法时间复杂度主要探究的是问题输入规模N的数量级 不是算法的具体执行次数

回顾上述1~100求和问题

//方案一
public class sum {
	public static void main(String[] args) {
		int s = 0;                            //执行一次
        int N = 100;                          //执行一次
		for (int i = 1; i <= N; i++) {        //执行N + 1 次
			s += i;                           //执行N次
		}
		System.out.println(s);                //执行1次
	}
 
}

//方案二
public class sum {
	public static void main(String[] args) {
		int N = 100;                    //执行1次
		int sum = (N + 1) * N /2;       //执行1次
		System.out.println(sum);        //执行1次
	}
 
}

        再次比较你会发现，对于方案一，其执行次数随着问题规模N的增长成线性正比。而对于方案二，其执行次数不会随着问题规模N增长。

常数阶O(1)：

        就是那些无循环、无递归、与问题输入规模N无关的、逐行执行的代码。如上述方案二。

图像：

 

线性阶O(n):

        与问题输入规模有关的，主要是一层循环的代码，多个一层循环可以并列但不能包含。如上述方案一。

图像：

 

线性阶O(n+m):

        和线性阶O(n)一样，只不过我们有两种数据的输入规模。如

public class test {
	public static void main(String[] args) {
		int N = 10;
		int M = 20;
		for (int i = 0; i <= N; i++) {
			System.out.println(i);
		}
		for (int i = 0; i <= M; i++) {
			System.out.println(i);
		}
	}
 
}

图像：

 

 

平方阶O():

        与问题输入规模有关的，主要是二层嵌套循环的代码。如下：

.

public class test {
	public static void main(String[] args) {
		int N = 10;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                System.out.println(i + j);
            }
        }
}

 图像：

 

平方阶O(nm):

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

public class test {
	public static void main(String[] args) {
		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);
            }
        }
}

图像：

 

 

对数阶O():

        与问题输入规模有关的，主要是一层循环迭代或递归的代码。如：

public class test {
	public static void main(String[] args) {
		int count = 1;
        int N = 100000;
        while (count < N) 
            count = count * 2;
 
}

图像：

常见 阶的比较