【算法与数据结构】4 算法利器,详解循环不变量与复杂度分析

简介: 【算法与数据结构】4 算法利器,详解循环不变量与复杂度分析

一、前情回顾

👉传送门:1 详解线性查找法

👉传送门:2 线性查找的优化

👉传送门:3 线性查找的测试

二、循环不变量

✳️循环是程序设计中非常重要的一种构建逻辑的方式,我们总是要循环的去做一件事情,逐渐的把算法想求解的问题给求解出来


1.通俗解析线性查找循环代码

对于前面学习的线性查找,只有一个重复循环:要做的是每一轮循环中确认一下data[i]是否是目标,如果data[i]和target是相等的,就把i给return回去,否则的话就继续进行这个循环

循环体中只有一个if语句,这个if语句执行完以后,相当于在这一轮循环中确认出了data[i]不是我们的目标,然后就进行下一次的循环

在每轮循环循环结束的时候能确定data[0…i]中没有找到我们的目标

public static <E> int search(E[] data, E target){

for(int i = 0; i < data.length; i ++)

 if(data[i].equals(target))

  return i;

return -1;

   }

1

2

3

4

5

6

2.线性查找循环的开始/末尾

微信图片_20230701104245.png


1️⃣在循环开始的时候,满足一个条件:data[0…i-1]没有找到目标


2️⃣当i等于0的时候,i-1就是-1——这个区间不存在,所以没有找到目标


3️⃣然后我们来判断data[0]是否是目标,如果data[0]不是目标的话,i++在下一轮循环中i变成了1,在i==1这轮循环开始的时候,i-1=0,也就是从0到0这一段区间中没有找到目标,相应的我们来判断data[1]是否是目标


4️⃣还不是目标的话,i++后,i就变成了2,i-1=1,也就是在i==2这轮循环开始的时候,从0到1这一段区间中没有找到目标

… …


✔️循环开始的时候 ,data[0…i-1]这段区间中没有找到目标,整个循环体是判断data[i]是否是目标


🟢如果data[i]是目标,return i

🔴如果不是目标,那么在这个循环末尾的时候就说明data[0…i]都没有找到目标

i++操作后,到了下一轮循环中,下一轮循环的i-1就是上一轮循环结束时的i

3.循环不变量的真面目

3.1 什么是循环不变量

✳️循环不变量其实就是指在每一轮循环开始的时候算法都满足这样的性质:对于上面的线性查找法来说,在每一轮循环开始的时候,都满足data[0…i-1]区间中没有目标target, 区间也可以表示data[0…i),这两种表示方法是等价的,循环每一轮开始的时候都一定是满足这样的一个条件的就叫做循环不变量


在上面的算法代码中,循环体其实就是判断一下data[i]是否是target,如果是的话就return了,如果不是的话,本轮循环就结束了,就要进行下一轮循环。


3.2循环体维持循环不变量

✳️依靠循环体,维持了循环不变量:


public static <E> int search(E[] data, E target){

for(int i = 0; i < data.length; i ++)

 if(data[i].equals(target))

  return i;

return -1;

   }

1

2

3

4

5

6

1️⃣在上面的算法代码中,循环体在做的事情,其实就是在维持这个循环不变量——经过了这轮循环体之后,要么整个循环结束了,完成了return i;要么循环继续,在下一轮循环中依旧满足[0,i-1]这个区间中没有找到目标。


2️⃣在循环结束的时候,如果i = data.length,对应到这个循环不变量中,就是data在[0,data.length-1]即在整个data中都没有找到目标,那么就return -1代表没有找到,如果找到了的话当然就是直接return i了


三、复杂度分析

1. 为何需要复杂度分析?

✅之所以要对算法做复杂度分析,是因为需要表示算法的性能


对于做同样的一个任务,我们会有不同的算法能够完成这个任务,对于不同的算法来说,他们的时间性能有差异,可以具体的用一个或者是一组测试用例对不同的算法都运行一下,实际的去比较一下他们的性能差异,但是这样的比较结果是有局限性的,因为无法保证运行不同的算法的这个计算机性能是完全一致的,甚至很难保证系统当时的状态都是完全一致的。而且这样做我们必须先把这个算法实际的实现出来才能看到它的性能。


❓很多时候有一个算法思想后,我们可不可能通过这个算法的思想就大致评估出算法的性能是优是劣、能否能够满足真正的业务需求再来决定是否要去实现它。


❗这些原因使得我们需要有一套工具能够非常抽象的从数学的层面就去判断一个算法它的性能是怎样的。


✔️为了解决上述需求,就产生了复杂度分析


2.复杂度分析如何表示算法性能?

依旧以前面线性查找的代码为例,分析它的复杂度


public static <E> int search(E[] data, E target){

for(int i = 0; i < data.length; i ++)

 if(data[i].equals(target))

  return i;

return -1;

   }

1

2

3

4

5

6

☑️**逻辑:**从头到尾遍历一次data这个数组,如果发现是我们要找到目标元素的话,返回对应的索引,否则的话整个for循环都走一遍,没有找到目标元素直接return -1


☑️时间:这个算法它执行的时间的多少,其实是和target出现在data中的位置相关的——target就在data[0]的位置,那么for循环执行一趟,算法直接结束,return i即可;如果target在data的末尾或者是target没有在data中,那么这个算法整个for循环从头到尾就都要执行一遍


☑️根据我们的测试用例的不同,算法实际执行的时间是不一样的


✔️对于复杂度分析来说,表示的是我们算法运行的上界,预估算法的性能,即不能比这更差了,通常是看最差的情况的


3.复杂度分析的运用

✳️对于前面线性查找的算法,算法运行的时间的大小,是和data数组中元素个数相关的


☑️通常我们对一个算法所作用的数据的大小叫做数据的规模,使用字母n表示——在线性查找法中,数据规模n就是数组data的大小,即data.length


☑️我们无需仔细的分析一轮循环对n个元素操作需要多少指令,我们只需要知道整个算法的性能和data数组的大小即数据规模n成一个正比的关系,把它记作大O,n级别的算法即O(n)


☑️在算法复杂度分析的世界中,常数是不重要的。


✴️复杂度描述的是随着这个数据规模n的增大算法性能变化的趋势


相关文章
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
69 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
29天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
32 4
|
1月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
19 0
数据结构与算法学习十四:常用排序算法总结和对比
|
1月前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
1月前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
18 0
|
24天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
9天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
10天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
11天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
|
10天前
|
机器学习/深度学习 算法 芯片
基于GSP工具箱的NILM算法matlab仿真
基于GSP工具箱的NILM算法Matlab仿真,利用图信号处理技术解析家庭或建筑内各电器的独立功耗。GSPBox通过图的节点、边和权重矩阵表示电气系统,实现对未知数据的有效分类。系统使用MATLAB2022a版本,通过滤波或分解技术从全局能耗信号中提取子设备的功耗信息。

热门文章

最新文章