【数据结构入门手札】算法核心概念与复杂度入门 - 指南
2025-12-17 14:29 tlnshuju 阅读(0) 评论(0) 收藏 举报
个人主页：聆风吟
系列专栏：数据结构入门手札
少年有梦不应止于心动，更要付诸行动。
文章目录
- 前言
- 一. ⛳️算法的定义
- 二. ⛳️算法的特性
- 2.1 输入
- 2.2 输出
- 2.3 有穷性
- 2.4 确定性
- 2.5 可行性
- 三. ⛳️算法设计要求
- 3.1 正确性
- 3.2 可读性
- 3.3 健壮性
- 3.4 时间效率高和存储量低
- 四. ⛳️算法效率的度量手段
- 4.1 事后统计方法
- 4.2 事前分析估算方法
- 五. ⛳️算法的复杂度
- 5.1 算法的复杂度的容易介绍
- 5.2 算法复杂度的重要性
- 全文总结
前言
简介：本系列重要记录个人从基础到进阶的学习总结，内容是消化知识点后的梳理，可能存在理解偏差，欢迎交流指正。希望给同为入门者的朋友提供一点参考，如果有发现错误的地方还请在评论区告知，一起学习进步，非常感谢！
本系列专栏：本期文章收录在《数据结构入门手札》，大家有兴趣允许浏览和关注，后面将会有更多精彩内容！
欢迎大家关注点赞收藏⭐️留言
一. ⛳️算法的定义
解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作就是算法：。简单说，算法就是 “解决问题的清晰流程”—— 就像菜谱（做菜的步骤）、导航路线（从 A 到 B 的路径），本质都是算法。
二. ⛳️算法的特性
算法具有五个基本特性：输入、输出、有穷性、确定性和可行性。
2.1 输入
算法具有0个或多个输入，尽管对于大多数算法来说，输入参数都是有必要的，但对于个别情况，如打印"hello world!"这样的代码，不需要任何输入参数，因此算法的输入可以是零个。
2.2 输出
算法至少有1个或多个输出，算法是一定需要输出的，如果不需要输出，我们还使用这个算法干嘛呢？输出的形式能够打印输出，也行是返回一个或多个值等。
2.3 有穷性
有穷性：是指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤都在可接受的时间内完成。死循环代码就是典型的不满足有穷性的情况。
2.4 确定性
确定性：算法的每一步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行的路径，相同的输入只能有唯一的输出结果。算法的每一步骤都被精确定义而无歧义。
2.5 可行性
可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。
三. ⛳️算法设计要求
说，处理同一个障碍，允许有多种解决问题的算法。通常为了设计一个 “好” 的算法应考虑达到以下目标：就是算法不是唯一的。也就
3.1 正确性
正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性，能够得到问题的正确答案。但是算法的 “ 正确 ” 一词在用法上通常有很大差别，大体分为以下四个层次：
- 算法应用没有语法错误；
- 算法程序对于合法的输入数据能够产生满足要求的输出结果；
- 算法程序对于非法的输入数据能够得出满足规格说明的结果；
- 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。
对于这四层含义，层次 1的要求最低，但仅仅没有语法错误实在谈不上是好算法。这就是如同仅仅解决温饱，不算是生活幸福一样。而层次 4是最难实现的，我们几乎不可能逐一验证所有的输入都得到正确的结果。所以一般情况下，我们通常把层次 3作为衡量一个算法算法是否合格的标准。
3.2 可读性
为了便于阅读，来理解和交流就是可读性：算法的另一个目的。可读性高有助于人们理解算法，晦涩难懂的算法往往隐含错误，不易被发现，并且难以调试和修改。
3.3 健壮性
健壮性：当输入内容不合法时，算法也能做出相关处理而不是产生异常或莫名其妙的结果。
3.4 时间效率高和存储量低
时间效率指的是算法的执行时间。对于同一个挑战，如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。算法在执行过程中需要的最大空间就是存储量需求指的，关键指算法程序运行时所占用的内存或外部硬盘存储空间。因此，设计算法时应尽量满足时间效率高和存储量低的需求。
四. ⛳️算法效率的度量方法
刚才我们提到了设计算法要提高效率。这里的效率大都指算法的执行时间。算法的执行时间必须依据该算法编制的脚本在计算机上运行时所消耗的时间来度量的。而度量一个程序的执行时间通常有有两种方法 —— 事后统计方法和事前分析估算方法。
4.1 事后统计方法
事后统计方法：此种方法主导是通过设计好的测试程序和数据，利用计算机计时器对不同的算法编制的软件的运行时间进行比较，从而确定算法效率的高低。不过这种方法明显是有很大的缺陷：
- 必须要依据算法事先编制好程序，这通常要需要花费大量时间和精力。如果编制出来发现它根本就是一团很糟糕的算法，那不就是竹篮打水一场空了吗？
- 时间的比较依赖计算机硬件和软件等环境因素的影响，有时会掩盖算法本身的优劣。
- 算法的测试数据设计困难，并且程序的运行时间往往还与测试数据的规模有很大关系，效率高的算法在小的测试数据面前往往得不到体现。
基于事后统计方法有这样那样的缺陷，我们一般不予以采纳，而是采用另一种事前分析估算方法。
4.2 事前分析估算途径
事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。经过分析大家可以发现，一个用高级程序语言编写的代码在计算机上运行时所消耗的时间取决于一下因素：
解析：第（1）条是一个好算法的根本，第（2）条要有软件来支持，第（4）条要看硬件性能。因此，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间，依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少。
五. ⛳️算法的复杂度
5.1 算法的复杂度的便捷介绍
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度关键衡量一个算法的运行快慢，而空间复杂度关键衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以大家如今已经不需要再特别关注一个算法的空间复杂度。
5.2 算法复杂度的重要性
复杂度在校招中的考察已经很常见，如下：
全文总结
本文主要讲解：
- 算法的定义：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
- 算法的特性：有穷性、确定性、可行性、输入、输出。
- 算法的设计要求：正确性、可读性、健壮性、高效率和低存储量需求。
- 算法的度量方法：事后统计途径、事前分析估算方法。
觉得文章还可能的话，希望能给个三连支持一下，就是今天的干货分享到这里就结束啦！若聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的协助就是作者前进的最大动力！