2018做网站的视频,许昌定制网站建设代理,seo外链工具下载,wordpress 顶部自定义[算法与数据结构] 一文详解线性查找法~#x1f4c5;前言一、#x1f4dd;算法基础知识1、什么是算法2、算法的五大特性二、#x1f4c8;线性查找法1、举例阐述2、实现线性查找法3、使用泛型4、升级改造5、使用自定义类6、循环不变量三、#x1f4ca;算法复杂度1、简单的复杂…
[算法与数据结构] 一文详解线性查找法~前言一、算法基础知识1、什么是算法2、算法的五大特性二、线性查找法1、举例阐述2、实现线性查找法3、使用泛型4、升级改造5、使用自定义类6、循环不变量三、算法复杂度1、简单的复杂度分析2、常见算法复杂度1遍历一个 **n * n** 的二维数组2遍历一个 a*a 的二维数组3数字n的二进制位数3、复杂度总结4、空间复杂度四、️测试算法性能五、 结束语彩蛋 One More Thing前言
众所周知算法与数据结构是所有计算机专业的同学必学的一门课程。算法不仅体现一个人的逻辑能力更体现一个人的思维能力。它不单是学习算法与数据结构更是深刻理解计算机科学。
那在本篇文章中我们就来给算法做个开篇并讲解最简单的一种算法线性查找法。叮开始讲解~
学完本篇文章你将会收获到
了解算法的基础知识了解线性查找法的基本思想使用 java 语言实现一个简单的线性查找法
一、算法基础知识
1、什么是算法
算法是一些列解决问题的清晰的可执行的计算机指令。
生活中无处不充满着算法比如说在路上问路说怎么去天安门那去天安门的各种路径就是一种算法。
或者说我们想问如何求解一元二次方程这个求解的方法也是一种算法。
还有可能是一道菜谱比如说如何做一道鱼香肉丝的菜。那它的各种做菜步骤我们也可以把它视为是一种算法。
2、算法的五大特性
算法有五大特性分别是
有限性 —— 对于一个算法来说它不应是无限循环的而应该在有限的时间里去执行完。所谓有限的时间不代表这个时间非常的短暂只要是一个确定的时间那么它就是有限的。确定性 —— 所谓确定性即不会产生二义性。比如说我们现在要面对一片数据这片数据描述的是一个班级中所有同学不同科目的考试成绩。那么我们在设计算法的时候有可能其中一个指令是拿出成绩最高的一个学生的分数。但这时我们没有明确是哪个科目的最高成绩在这个时候程序就会产生二义性。因此在设计算法时我们应该明确其具体指令。可行性 —— 算法中的每一步应该都是可行的。举个例子假设现在有一个算法这个算法明确的是拿出最大的质数。但其实质数是有无穷个不可能拿出最大的。所以这个算法是不可行的。输入 —— 对于一个算法来说它肯定是有它需要操作的对象那么它所操作的这些对象就是算法的输入。输出 —— 一个算法在执行完成后总会有一个具体响应的结果那么这个结果就是它的输出值。
二、线性查找法
1、举例阐述
线性查找法可以说是最简单的一种算法。那它是什么呢举个例子
假设现在有一沓卷子我们要在这沓卷子中找到属于自己的那张卷子。那么线性查找法的方法寻找的话将按照下面的步骤
第1张不是第2张不是第3张不是……第5张是找到了
如大家所看到的线性查找法就是线性的按照顺序一个个地去寻找。
2、实现线性查找法
假设现在有一组数组我们要在数组中查找到某个具体数值的索引。那用线性查找法的方式如何查找呢首先我们新建一个 java 项目并在项目的 src 文件夹下新建一个 java 类命名为 LinearSearch 。具体代码如下
public class LinearSearch {// data 是一个数组target 是我们要查找的目标// 括号里面是函数声明public int search(int[] data, int target) {// 线性查找逻辑for (int i 0; i data.length; i) {if (data[i] target)return i;}return -1;}public static void main(String[] args) {int[] data {24, 45, 67, 12, 465, 78, 68};LinearSearch ls new LinearSearch();int res ls.search(data, 12);System.out.println(res);int res2 ls.search(data, 888);System.out.println(res2);}
}
此时控制台的输出为
3
-1大家可以看到我们要找 12 这个数它在第 4 个位置也就是索引为 3 的位置。还有另外一个数是 888 但是 888 并没有出现在数组中所以返回 -1 。
但是呀大家有没有发现这个程序看着虽然是实现了但它还好像又有很多存在的新问题。是什么呢
当前存在的问题是我们只能在一个 int 型的数组中查找一个 int 型的元素。但是在 java 语言中单单基本类型就有8种。更不用提我们用户还可以自己创建各种各样的类每个类都可以看作是一个新的类型。那我们就更不可能去每个类都写一个 search 方法对吧。
因此对于这样子的问题我们要如何解决呢
这个时候我们要使用到 java 语言中的泛型。接下来我们将依据泛型来进行改造升级。
3、使用泛型
在这里我们先简单的复习一下 java 的基本数据类型。具体如下
在 java 语言中的泛型只能接受类对象而不能接受基本数据类型。java 中的 8 中基本数据类型为 boolean 、 byte 、 char 、 short 、 int 、 long 、 float 和 double 。由于泛型只能接受类对象因此为了应对这种状况 java 语言对每一种基本数据类型都做了一个对应的包装类。那么这些数据类型和他们所对应的包装类之间可以进行相互的转换。其中 8 种对应的包装类分别为 Boolean 、 Byte 、 Character 、 Short 、 Integer 、 Long 、 Float 和 Double 。有了包装类的概念那么在使用泛型的时候如果我们想传入的类型是上面第①点中的基本数据类型最终只需要将这些数据类型转换成它们的包装类即可使用。
4、升级改造
上面我们简单了解了 java 语言中泛型的一些基本信息那现在我们用所学到的泛型来改造原先例子里的代码。具体代码如下
public class LinearSearch {private LinearSearch() {}// 静态方法public static E int search(E[] data, E target) {// 线性查找逻辑for (int i 0; i data.length; i) {// 判断的是引用相等equals 判断的是值相等if (data[i].equals(target))return i;}return -1;}public static void main(String[] args) {Integer[] data {24, 45, 67, 12, 465, 78, 68};int res LinearSearch.search(data, 12);System.out.println(res);int res2 LinearSearch.search(data, 888);System.out.println(res2);}
}
此时控制台的输出为
3
-1通过这种方式我们让这个算法的灵活性又加强了一点点。
5、使用自定义类
上面我们对线性查找有了基础的了解现在大家来思考一个问题我们是否可以自己设计一个 Student 类这个类里面呢有什么样的成员变量都无所谓之后呢基于 Student 类的设计自己定义这个类里面的 equals 函数。
接下来将依据上面这个题目来进行代码编写
首先在项目的 src 目录下新建一个 Student 类具体代码如下
public class Student {private String name;public Student(String name) {this.name name;}Overridepublic boolean equals(Object student) {if(this student) {return true;}if(student null)return false;if(this.getClass() ! student.getClass())return false;Student another (Student)student;return this.name.equals(another.name);}
}
接下来继续改造上面的 LinearSearch.java 具体代码如下
public class LinearSearch {private LinearSearch() {}// 静态方法public static E int search(E[] data, E target) {// 线性查找逻辑for (int i 0; i data.length; i) {// 判断的是引用相等equals 判断的是值相等if (data[i].equals(target))return i;}return -1;}public static void main(String[] args) {Integer[] data {24, 45, 67, 12, 465, 78, 68};int res LinearSearch.search(data, 12);System.out.println(res);int res2 LinearSearch.search(data, 888);System.out.println(res2);Student[] students {new Student(Monday),new Student(Tuesday),new Student(Wednesday)};Student tuesday new Student(Tuesday);int res3 LinearSearch.search(students, tuesday);System.out.println(res3);}
}
现在我们来看下控制台的输出结果
3
-1
1大家可以看到上面输出的依然是 3 和 -1 。最后一个输出的 1 是我们自定义的 Student 类所输出的结果。这样看来整个程序的灵活性又增强了。
6、循环不变量
继续我们依旧根据线性查找这个算法来学习循环不变量。循环不变量这个概念听起来似乎有点理论。但实际上当我们在使用算法时如果能够很好的运用这个概念无论是对算法的理解还是真正在写算法的时候都能够使得我们更加容易地写出正确的算法。
循环是程序设计中非常重要的一种构建逻辑的方式。实际上大家在设计算法的时候近乎所有的算法都会有循环这个概念。我们总是要循环地去做一件事情逐渐地把我们当下在求解的算法给求解出来。
比如说对于下面这个最简单的线性查找法
public staticE int search(E[] data, E target) {for(int i 0; i data.length; i)if(data[i].equals(target))return i;return -1;
}那上面这个算法的循环不变量指的是什么呢指的是 for(int i 0; i data.length; i) 这一串。
所谓循环不变量指的是在每一轮开始的时候循环的条件是不变的。大家可以想象一下每回 if 语句如果在执行时无法在 data[i] 中匹配具体 target 的值那么就会接着继续下一个 for 循环而这个 for 循环所执行的内容一直都是在 [0…i) 这个区间内因此称它为循环不变量。
在上面的这段算法中其中的一段代码
if(data[i].equals(target))return i;这段代码称为是循环体主要作用是维持循环不变量。
三、算法复杂度
下面我们来讲一下算法的复杂度。
1、简单的复杂度分析
我们为什么要对算法做复杂度分析呢其实是为了用来表示算法的性能。
比如说对于同样的任务我们将会有不同的算法来完成这个任务而不同的算法在时间性能上也有一定的差异因此我们需要对算法做复杂度分析来求解出最优的算法。
复杂度描述的是随着数据规模 n 的增大算法性能的变化趋势。
2、常见算法复杂度
下面我们来看集中常见的算法复杂度。
1遍历一个 n * n 的二维数组
具体算法代码如下
for(int i 0; i n; i)for(int j 0; j n; j)// 遍历到 A[i][j]上面这个算法的时间复杂度为 O(n²) 。
2遍历一个 a*a 的二维数组
其中a * a n 具体算法代码如下
for(int i 0; i a; i)for(int j 0; j a; j)// 遍历到 A[i][j]上面这个算法的时间复杂度为 O(a * a) 也就是 O(n) 。在这种场景下我们要明确 n 是谁。
3数字n的二进制位数
具体算法代码如下
while(n) {n % 2 // n 的二进制中的一位n / 2
}对于这个算法来说其时间复杂度为 O(log2n)O(log_2n)O(log2n) 那如果是要算 n 的十进制位数呢其时间复杂度为 O(log10n)O(log_{10}n)O(log10n) 。但值得注意的是不管是 以 2 为底还是以 10 为底的算法复杂度都统一为 O(logn)O(logn)O(logn) 。因为在程序的算法中这个底的差别对实际的算法并没有特别大的影响所以都统称为 O(logn)O(logn)O(logn) 的复杂度。
3、复杂度总结
下面对常见几种算法的复杂度进行总结
O(1)O(logn)OnO(nlogn)O(n²)O(2n)O(n!)O(1)O(logn)O\sqrt{n}O(nlogn)O(n²)O(2^n)O(n!)O(1)O(logn)OnO(nlogn)O(n²)O(2n)O(n!)
4、空间复杂度
当谈到时间复杂度时我们还会不由自主的想起空间复杂度。但对于现代的计算机来说硬盘存储容量越来越大这个时候空间复杂度就显得没有那么重要了。所以我们通常通过空间换时间的方式来让程序得以更优解。
四、️测试算法性能
依然以上面我们讲到的 LinearSearch 为例接下来我们来测试算法性能。显然在上面的算法中只有 10 位数左右但是在实际的开发中计算量肯定是不止这么小的。一般是小到十万级大到千万级和亿万级不等。接下来我们用上面的例子来进行改造首先在 src 目录下新建一个 ArrayGenerator 的 java 类具体代码如下
public class ArrayGenerator {private ArrayGenerator() {}public static Integer[] generateOrderArray(int n) {Integer[] arr new Integer[n];for(int i 0; i n; i)arr[i] i;return arr;}
}接着我们来改造 LinearSearch 这个类具体代码如下
import java.lang.reflect.Array;public class LinearSearch {private LinearSearch() {}// 静态方法public static E int search(E[] data, E target) {// 线性查找逻辑for (int i 0; i data.length; i) {// 判断的是引用相等equals 判断的是值相等if (data[i].equals(target))return i;}return -1;}public static void main(String[] args) {// 想要取出的数据规模int[] dataSize {1000000, 10000000};for(int n: dataSize) {Integer[] data ArrayGenerator.generateOrderArray(n);long startTime System.nanoTime();// 运行 100 次的时间for (int k 0; k 100; k)LinearSearch.search(data, n);long endTime System.nanoTime();double time (endTime - startTime) / 1000000000.0;System.out.println(n n , 100 runs : time s);}}
}此时控制台的显示结果为
n 1000000, 100 runs : 0.3463959s
n 10000000, 100 runs : 3.3792709s大家可以看到当 n 是 100万 的数据时最终运行时间大约为 0.3s 而当数据为 1000万 时最终运行的时间大约为 3.3s 。它们两者之间的差距大约是 10 倍左右也就是说呈线性增长。
五、 结束语
再上面的文章中我们学习到了算法的基本知识同时还了解了线性查找法的基本思想。在此基础上简单实现了线性查找法并使用泛型和自定义类升级改造了线性查找法。
最后我们还简单介绍了算法的复杂度分析以及对我们所写的算法进行了性能测试。
到这里关于本文的介绍就结束啦不知道大家对线性查找法是否有一个更深的了解呢
彩蛋 One More Thing 关注公众号 星期一研究室 第一时间关注学习干货更多精选专栏待你解锁~如果这篇文章对你有用记得留个脚印jio再走哟~我们下期见
