数据结构和算法概述
1.1什么是数据结构
一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。
数据结构就是把诗句元素按照一定的关系组织起来的集合,用来组织和存储数据。
1.2数据结构的分类
数据结构可以分为逻辑结构和物理结构两大类
-
逻辑结构的分类(按照不同元素之间的关系区别)
- 集合结构:集合结构中的数据元组属于同一个集合,其他无任何关系
- 线性结构:元素之间的关系为一对一
- 树形结构:一对多
- 图形结构:多对多
-
物理(存储)结构的分类(逻辑结构在计算机中真正的表示方式(又称为映像))。
-
顺序存储结构(连续的内存单元,元素都有自己的索引)
访问简单,增删麻烦
-
链式存储结构(内存单元不确定,元素之间靠指针连接)
增删简单,访问麻烦
-
1.3算法
算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。
根据一定的条件,对一些数据进行计算,得到需要的结果。
优秀的算法有两个追求:
- 花最少的时间完成需求;
- 占用最少的内存空间完成需求 ;
1.4算法初识
计算n的阶乘;
package com.zebra.chapter01;
//计算10的阶乘
public class Demo01 {
//解法一:for循环
public static long solution1(int n){
long result = 1;
for (int i = 0; i < n; i++) {
result*=(i+1);
}
return result;
}
//解法二:递归
public static long solution2(int n){
if(n==1)
return 1;
else
return n*solution1(n-1);//有long型整个表达式自动转换成long型
}
public static void main(String[] args) {
int n = 20 ;
System.out.println(solution1(n));
System.out.println(solution2(n));
}
}
分析:解法一相对优于解法二,解法一和解法二运行的时间没有明显差异,但是解法二每递归一次就会开辟一个新的方法空间,占用的内存更多。