当前位置：首页 > news >正文

day2:算法之美|打开算法之门与算法复杂性

news 来源：原创 2024/4/25 15:53:20

14天阅读挑战赛

系列文章目录

后续补充完善

文章目录

系列文章目录
课程概览
一、算法特性
二、什么是好的算法
- 2.1 正确性
- 2.2 易读性
- 2.3 健壮性
- 2.4 高效性
- 2.5 低存储性
- 2.6 交互性
三、算法的复杂度
- 3.1 算法的时间性能分析
- 3. 2 空间复杂度
四、总结

课程概览

tip：对算法及算法复杂度有一个认知。

数据结构+算法=程序
算法是对特定问题求解步骤的一种描述。
以下是整理的章节的思维导图：
课程概览

一、算法特性

算法的特性
算法的五个基本特性分别是：输入、输出、有穷性、确定性和可行性。

(1)输入/输出：算法具有零个或多个输入，算法至少具有一个或多个输出。
(2)有穷性：是指算法在执行有限的步骤后，自动结束而不会出现无限循环，并且每个步骤在可接受的时间内完成。
(3)确定性：算法的每个步骤都有明确的含义，不会出现二义性。
(4)可行性：算法的每一步都必须是可行的，也就是说，每一步都通过执行有限次数完成。

举个栗子：
一张图说明算法
把这个流水线视同于一个算法：
确定性：目标是生产小黄人，整个算法也就是为这个服务的。如果生产出来的是史莱姆就有问题，需要去排查纠错。
输入：香蕉
输出：小黄人
可执行性：算法的每一个步骤，也就是产线的每一个环节，必须运行正常，输入后才能有正确的输出。
有穷性：有多少香蕉就会产生对应比例的小黄人，没有香蕉就停止，不生产了。

二、什么是好的算法

一张图表示好的算法应该具备的特性：
tip：保持独立思考，不断向自己提问，书中是5种特性，但是个人认为作者把系统或者算法的稳定性（鲁棒性）和与用户的交互的错误提示给搞混了，因此我在自己的笔记中，增加了鲁棒性和交互性。作为一名产品，以用户为中心，是我一直以来坚持的东西，由于最终用户是人，所以在图形交互界面和算法设计时，给出用户便于理解和操作的提示。所以讲特性归纳为交互性，仅代表个人观点。
在这里插入图片描述

2.1 正确性

正确性是指算法能够满足具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期。

2.2 易读性

算法遵循标识符命名规则，简洁易懂，注释语句恰当适量，方便自己和他人阅读，便于后期调试和修改。

一段好的算法代码：
好的代码习惯
步骤清晰，缩进合适。备注简明扼要，让人一目了然，降低了阅读障碍，符合人的视觉认知习惯

下面再来看一段屎山代码：

public static void main(String[] args) {
    int a = args.length;
    int b = 42 / a;

    if (a == 1) {
      a = a / (a - a);
    }
    if (a == 2) {
      int c[] = {1};
      c[42] = 99;
    }
}
上边的代码很直率，既不考虑 a 可能为 0 的情况，也不考虑数组越界。直来直去，兄弟，你这样我很难搞啊。

接手和研读一堆屎山代码是很痛苦的事情，己所不欲勿施于人，相信都有遇到这种抓狂的情况。个人认为技术的核心技能是解决问题的能力和思维，而不是堆码量，活做细点后面可以减少很多麻烦，有了良好的习惯和思路，到哪里都能快速体现自己的价值。
在这里插入图片描述

2.3 健壮性

指一个系统或者算法在受到外部扰动或内部参数摄动等不确定性因素干扰时，系统扔保持其结构和功能稳定。
我们来参考两个个机器人系统，我们希望机器人从A点像B点行进，如果中途机器人倒下，一号机器人只能停下，但二号机器人可以自行的爬起继续像B点前进，我们就认为一号机器人不具有鲁棒性，而二号有较好的鲁棒性。
在这里插入图片描述
图形识别算法中，对抗性扰动的算法和训练，就是算法的鲁棒性应用。
还有在实际应用的过程中，比如运行实例的重启，加最大计算数量限制强行停止，超过等待时间中断等算法就是为此而诞生的。

2.4 高效性

高效性是指算法运行效率高，即算法运行所消耗的时间短。也就是通常意义的时间复杂度。

2.5 低存储性

低存储性是指算法所需的存储空间小。对于像手机、平板电脑这样的嵌入式设备，算法如果占用空间过大，则无法运行。算法占用的空间大小被称为空间复杂度。

2.6 交互性

算法对非法数据及操作有较好的反应和处理。例如，在学生信息管理系统中登记学生年龄时，若将21岁误输入为210岁，则系统应该有错误提示。
还有类似邮箱、身份证、电话号码、密码强度等验证算法都是如此。
除了（1）～（3）中的基本标准之外，好算法的评判标准是高效率、低存储。

三、算法的复杂度

个人是从软件二次开发开始学习系统学习程序开发的，之前的要求是能跑，但是现在到产品岗后，日常工作中也需要找到性能瓶颈，除去网络延时，服务器CPU,内存大小，硬盘I/O，SQL执行效率等，程序的算法也是一个重要的指标，需要对其有足够的认识，
在这里插入图片描述

3.1 算法的时间性能分析

(1)算法耗费的时间和语句频度

一个算法所耗费的时间=算法中每条语句的执行时间之和。

每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间。
时间复杂度有一些评价标准：
在这里插入图片描述

符合常数型函数曲线特性的算法
最好的时间复杂度就是O(1)，O(1)表示在一个常数时间，并且是只要一条语句就能执行完的功能，它的时间开销是就O(1)常数时间是一条直线，你的元素规模不管是1个、2个、3个、4个、还是100个、1000个它所需要的时间都是恒定的如果程序达不到O(1)的性能，但能达到一个常数级别O(2)、O(3)、O(4)、O(5)也是很好的，也就是说你不管程序的规模怎么样，只要固定的只需要一条、两条、三条、四条或者五条语句，或者是固定的语句数量就能完成，
符合对数性函数曲线特性的算法
差一点的情况是O(logn)，它是一条弧线，当元素个数增加时，算法的程序性能消耗并没有快速地增加，而是增加的速度越来越缓慢，这种程序性能也不错再差一点就是一条斜线，什么意思？随着元素个数的增加，运算时间也增加，这种就没有O(logn)好，因为O(logn)是元素越多，时间开销反而增加的没那么厉害，线性时间还会增加。
符合指数型函数曲线特性的算法
那比较不好的是什么呢？就是O(n)的平方，大家还记得中学里学过的O(n)的平方是一条什么样的曲线吗？它是一条开口朝上的抛物线，这个抛物线就是随着你的程序规模增加，程序的运行时间会显著的增加，这就非常不好了为什么？因为它就意味着你的程序，在元素个数少的时候跑得比较快，元素个数越多跑得就越慢那如果是n的三次方呢？那就更糟糕了，五次方、十次方也一样，这就是我们衡量性能的标准

用最直白的话来说：一般开发应用中看：循环嵌套几层，每一层的循环次数和哪个变量有关？

3. 2 空间复杂度

空间复杂度就看你申请内存用了多少(数组长度)，与哪个变量有关O(),logn中对数函数的底数是多少一般来说是 222 。因为计算机中很多地方采用的是二分法。当然，如果非要三分、四分法解决问题，那么底数就相应变成3、4但是，其实 O(log2n)=O(log3n/log23)=O(log3n)O(log_2n)=O(log_3n/log_23)=O(log_3n)O(log_2n)=O(log_3n/log_23)=O(log_3n) (常数可以扔掉)，所以你爱写啥都随便。
递归算法：包括了递推和回归两个步骤。
课程这里提到了内存堆栈的概念，可以和队列对照学习，效果更加。