【算法与数据结构】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的增大算法性能变化的趋势


相关文章
|
24天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
60 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
12天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
20天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
31 4
|
19天前
|
算法
PID算法原理分析
【10月更文挑战第12天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
|
21天前
|
移动开发 算法 前端开发
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
19 0
|
25天前
|
算法
PID算法原理分析及优化
【10月更文挑战第6天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
|
27天前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
27天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
17 0
|
5天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
63 9
|
2天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。