算法基础

小咪咪 2023-10-05 17:42 51阅读 0赞

在 [数据结构基础][Link 1] 中，简单说了下数据结构相关的东西：比如数据、数据项、数据对象。这篇文章将介绍一些算法上的东西。

这篇文章例子可能不如上一篇的多或者生动，还是那句话：感觉记概念不如记例子，毕竟没必要深挖严格的定义，但是概念还是要理解的~

--------------------

### 算法 ###

算法是解决 `特定问题` 的`步骤描述`，放在计算机中的话，表现为指令的有限序列，每个指令对应一个或多个的操作。往广义上说：算法就是操作数据的方法。

比如要对一个数组中的元素排序，咱们得写一些代码，这些代码对应好多操作，每个操作对应了功能，这就算是算法了。

### 算法特性 ###

输入输出：有零个或多个输入（比如打印一句话，输入参数个数为 0 个）；输出是一定要有的，要不写那个算法做啥呢，不就是为了解决某个问题然后显示下结果吗（比如打印、或者 return 数值）。

有穷性：指的是执行完有限的步骤后，代码会自动结束不会出现死循环，当然也要在可接受的时间点内完成。不能说我打印个 hello world 打印了上下五千年吧。

确定性：算法的每步骤都是有确定含义的，不能有二义性。

可行性：每个步骤都是可行的，或者说每一步都能通过执行有限的次数完成。

### 算法要求 ###

正确性：指算法至少具有输入、输出、处理步骤确定性、能正确反映问题需求并能得到问题的正确答案。

> 没有语法错误->可执行步骤正确性  
> 有输入和输出结果->正确的输入和不正确的输入都有与之对应的输出  
> 比如让你写个降序排列的，你写了个升序的，那就不对了……

可读性：方便阅读、理解和交流。

健壮性：输入数据不合法，也能做出相应处理，而不是产生异常或者杂七杂八的结果（比如写排序，如果不给你数组，你也得输出类似「输入数据」异常的结果）。

时间效率高：就是执行时间短（效率= 工作量÷工作时间）。

存储量低：就是用的存储成本低。

### 算法效率度量方法 ###

事后统计方法：就是通过执行设计好的测试程序和数据，然后利用计算机的计时器来获得执行时间，从而对比不同算法的效率。但是有着明显的缺陷：

1.  执行和计算机硬件和系统环境有个巨大关系，不同的算法跑在搭载不同 CPU 的计算机上效率没法比，哪怕同一个配置，但是也存在 CPU 利用率等差异，算法的效率也没法比较，只能有个大概的结果；
2.  如果写出了算法而且跑了才知道具体的效率，如果效率极低，那算法就相当于白写了；
3.  为了比较算法效率高低，选多少数据量也是问题，如果 10 个数字排序，算法之间没什么差异，如果 1000 万个数字呢。

事前分析估算法：就是在算法执行前（不用测试）肉眼估算。既然我们知道计算机硬件和软件对算法执行时间有影响，我们就先抛开这些第三方因素不谈，是不是可以知道与算法的效率和算法本身以及输入数据的多少有关了；咱们再把数据量设为固定的，是不是知道算法效率是十分依赖与算法本身了。

下面看个对比：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]

都是求「从 1 加到 100 的和」，方式一执行了 1+(n+1)+n+1= 2n+3 次，方式二执行了 1+1+1=3 次。然后我们把两个方式中都有的第一次和最后一次去掉，再把循环判断的开销去掉，方式一和方式二的差距就是 n 次和 1 次的差距了。显然方式二更好。

--------------------

关于算法，还有重要的 [时间复杂度][Link 2] 和 [空间复杂度][Link 3] 已经出炉了，欢迎前去阅读斧正。

[Link 1]: https://mindartisan.blog.csdn.net/article/details/112595207
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210116033349803.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4,size_16,color_FFFFFF,t_70
[Link 2]: https://mindartisan.blog.csdn.net/article/details/112691301
[Link 3]: https://mindartisan.blog.csdn.net/article/details/113058696