为何你的算法总是比别人的慢？【21天算法系列】之顺序查找算法【Java 版】

​

🚀个人主页：欢迎访问Ali.s的首页

⏰ 最近更新：2022年8月1日

⛽ Java框架学习系列：【Spring】【SpringMVC】【Mybatis】

🔥 Java项目实战系列：【飞机大战】【图书管理系统】

🍭 Java算法21天系列：【查找】【排序】【递归】

⛳ Java基础学习系列：【继承】【封装】【多态】

🏆 通信仿真学习系列：【硬件】【通信】【MATLAB】

🍄 个人简介：通信工程本硕🌈、Java程序员🚴。目前只会CURD😂

💌 点赞 👍 收藏 💗留言 💬 都是我最大的动力💯

活动地址：CSDN21天学习挑战赛

文章目录

一、什么是算法

如果想要成为一名优秀的程序员，除了需要掌握一门编程语言之外，更重要的是多动手实践，实践是学习的最好老师，当你的代码达到一定的量时，无形之中提升自己解决问题的能力。编程语言有很多，例如大多数人入门的

C语言

，曾经火过的

PHP

，需求很大的Java以及当前热门的

Python

等，其实任何一门编程语言的学习，本质就是学习它固有的语法知识，然后通过不同的应用，去解决遇到的问题，整个过程或许只能死记硬背，几乎没有别的什么捷径可走。但是，掌握算法的知识，能够帮助你提升解决问题的能力，进而凸显出还是有捷径可循。

提到

【算法】

，我想很多人的第一感觉是觉得它高深莫测、十分难懂，其实在生活、工作、学习中，到处都有算法的影子，比如当你过红路灯路口时，为什么会在一定时间内每个方向的红绿灯会交替变化呢？当你在家中用洗衣机洗衣服时，为什么你只需要按几个按钮，洗衣机就能帮你完成洗衣服的任务呢？其实类似的场景的背后，都是有程序算法的运用。简而言之，算法就是说明了你遇到的某个问题的具体步骤，先做什么、再做什么、最后做什么，只要依次完成这些步骤，那么问题就可以得到解决。下图能够清楚地很好的回答你你算法是什么？

当你知道算法是什么的时候，你会发现每个人遇到同一个问题的时候，会出现处理步骤不同的情况，这就是算法最具魅力的地方，只要能够解决问题，具体怎么做都不重要，但是这便引出了，谁的算法更好？谁的算法更快？那种算法更优？等一系列问题。那么如何去衡量算法的优劣，我们主要看算法的时间复杂度和空间复杂度，这就是为什么在很多编程比赛中，都会有数据量级的要求，内存空间的约束以及运行时间的限制。

二、时间复杂度

判断一个算法所编程序运行时间的多少是衡量时间复杂度的标准，而并不是将程序编写出来，在计算机上运行所消耗的时间来度量。因为解决一个问题的算法因人而异，必然会有很多种，但是具体实现的工作量肯定是巨大的，由于不同计算机的软、硬件环境不同，即使用同一台计算机，不同时间段的计算机系统环境也不相同，程序的运行时间都可能会受影响，那么，如何预估一个算法所编程序的运行时间呢？其实很简单，先分别计算程序中每条语句的执行次数，然后用总的执行次数间接表示程序的运行时间，就能够预估出程序的运行时间。下面举个简单的例子，常见的

for循环

：

for(int i =0; i < n ; i++){
    k++;}

循环变量

i

从

0

到

n

，执行

n+1

次，而

k

执行

n

次增加，所以所有的语句被执行了

2n+1

次，对于其他的循环来说，以此类推就可以得到执行的次数，时间复杂度常用大写

O

符号表示，所以对于单层

for循环

来说，时间复杂度为

O(n)

，那么进一步推出对于双层

for循环

来说，其时间复杂度为

O(n²)

，常见的时间复杂度排序为：

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

三、空间复杂度

空间复杂度其实与时间复杂度类似，但是计算起来可能相对要考虑的更多了，要知道每一个算法所编写的程序，运行过程中都需要占用大小不等的存储空间，代码本身所占用的存储空间，程序中输入输出数据，也会占用一定的存储空间，在运行过程中，涉及到需要临时申请更多的存储空间来储存变量等所占用的空间。

首先，程序自身所占用的存储空间取决于其包含的代码量，如果要压缩这部分存储空间，就要求我们在实现功能的同时，尽可能编写足够短的代码，那这就要求使用高效的算法或者数据结构处理代码。其次运行过程中输入输出的数据，往往所遇到的问题而定，这个可能无法改变或者说差距不大，即便所用算法不同，程序输入输出所占用的存储空间也是相近的。最后，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间。不同的算法所编写出的程序，其运行时申请的临时存储空间通常会有较大不同，中间需要的变量等都会占用大部分的空间内存，所有的标记存储之类的代码底层不能凭空存在。举个例子：

Java

中的输入

Scanner sc=newScanner(System.in);int k=sc.nextInt();

到我们创建Scanner输入扫描器时，需要设置变量k来用于接收输入的值，这是就需要申请临时的空间给k使用，这便涉及到空间复杂度，在大型的编程比赛中，常常会出现时间复杂度超出范围，而空间复杂度很小，所以经常是牺牲空间复杂度来换取时间复杂度。如果空间复杂度超出范围，大部分是程序写得过于复杂或者代码错误。

四、顺序查找

顺序查找的查找过程为：从表中的最后一个数据元素开始，逐个同记录的关键字做比较，如果匹配成功，则查找成功；反之，如果直到表中第一个关键字查找完也没有成功匹配，则查找失败。其过程十分简单，下面给我动态模拟效果：

动态模拟顺序查找

查找操作的性能分析主要考虑其时间复杂度，而整个查找过程其实大部分时间花费在关键字和查找表中的数据进行比较上。所以查找算法评判的依据为：查找成功时，查找的关键字和查找表中的数据元素中进行过比较的个数的平均值。

总结

以上就是今天要讲的内容，针对为何你的算法比别人慢的原因做了分析，动态展示了下顺序查找算法，一个个比较，最终查找到需要的值。

​