【愚公系列】软考中级-软件设计师 054-算法设计与分析（算法分析基本概念与算法分析基础）
🏆 作者简介，愚公搬代码
🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，CSDN商业化专家，阿里云专家博主，阿里云签约作者，腾讯云优秀博主，腾讯云内容共创官，掘金优秀博主，51CTO博客专家等。
🏆《近期荣誉》：2022年度博客之星TOP2，2023年度博客之星TOP2，2022年华为云十佳博主，2023年华为云十佳博主等。
🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏
🚀前言
算法在现实中有许多应用场景，以下是其中的一些例子：
| 应用场景 | 算法 |
|---|---|
| 搜索引擎 | PageRank算法、TF-IDF算法 |
| 推荐系统 | 协同过滤算法、基于内容的推荐算法 |
| 图像处理 | Canny边缘检测算法、Haar特征检测算法 |
| 机器学习 | 神经网络、决策树、支持向量机 |
| 路径规划 | Dijkstra算法、A*算法 |
| 数据压缩 | Huffman编码、Lempel-Ziv-Welch（LZW）算法 |
| 调度和优化 | 贪心算法、动态规划 |
这只是一小部分算法在现实中的应用场景，实际上算法在各个领域都有广泛的应用。算法的目标是提高效率、减少资源消耗、优化结果等，为我们的现实生活和计算机应用提供了重要的支持。
🚀一、算法分析基本概念
🔎1.算法的概念
算法是用于解决问题或执行任务的一系列有序步骤的描述。它描述了在给定输入条件下，计算机应该如何进行操作来产生所需的输出结果。算法可以看作是问题解决的具体步骤，它是一种确定性的过程，通过一系列指令来处理输入数据并产生输出结果。
一个好的算法应该具备以下特点：
| 特性 | 描述 |
|---|---|
| 有穷性 | 算法在执行有穷步之后必须结束，并且每一步都可以在有穷时间内完成。 |
| 确定性 | 算法中的每一条指令必须有确切的含义，没有二义性，并且对于相同的输入只会得出唯一的输出。 |
| 可行性 | 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。 |
| 输入 | 一个算法可以有零个或多个输入，这些输入来自于某个特定对象的集合。 |
| 输出 | 一个算法可以有一个或多个输出，这些输出与输入有着特定关系。 |
算法可以用自然语言、图表、伪代码或编程语言等方式进行描述和表示。它在计算机科学中起着至关重要的作用，是构建各种应用程序和系统的基础。
🔎2.算法的表示
常用的表示算法的方法有自然语言、流程图、程序设计语言和伪代码等
| 方法 | 描述 |
|---|---|
| 自然语言 | 优点是容易理解，缺点是容易出现二义性，并且算法通常很冗长。 |
| 流程图 | 优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言。 |
| 程序设计语言 | 优点是能直接用计算机执行，缺点是抽象性差，会导致算法设计者忽略“好”算法和正确逻辑的重要性，并需要掌握编程技巧和语言。 |
| 伪代码 | 伪代码介于自然语言和程序设计语言之间，结合某一程序设计语言的基本语法，同时采用自然语言来表达，可以最简明扼要地表达一个给定的算法。 |
🚀二、算法分析基础
🔎1.时间复杂度
时间复杂度是一种用于衡量算法运行时间的度量方法，它表示随着输入规模的增加，算法所需的时间增长的趋势。
时间复杂度通常用大O符号（O）来表示，它表示算法运行时间的上界。具体来说，如果一个算法的时间复杂度为O(f(n))，表示随着输入规模n的增加，算法最坏情况下的运行时间不会超过一个与f(n)成正比的函数。
以下是常见的时间复杂度及其示例：
-
常数时间复杂度 O(1)：无论输入规模大小如何，操作所需的时间都是固定的。
示例：访问数组中的某个元素。 -
线性时间复杂度 O(n)：随着输入规模n的增加，算法需要的时间正比于n。
示例：遍历一个长度为n的数组。 -
对数时间复杂度 O(log n)：随着输入规模n的增加，算法需要的时间增长缓慢，增长速度小于线性时间复杂度。
示例：二分查找算法。 -
线性对数时间复杂度 O(n log n)：随着输入规模n的增加，算法需要的时间增长更快一些，但增长速度小于平方时间复杂度。
示例：快速排序算法、归并排序算法。 -
平方时间复杂度 O(n^2)：随着输入规模n的增加，算法需要的时间呈平方级增长。
示例：冒泡排序算法、选择排序算法。 -
指数时间复杂度 O(2^n)：随着输入规模n的增加，算法需要的时间呈指数级增长。
示例：旅行商问题的穷举解法。
在实际应用中，我们希望选择时间复杂度较低的算法来解决问题，以提高算法的效率和性能。因此，正确评估和理解算法的时间复杂度至关重要。
🔎2.空间复杂度
空间复杂度是指算法在运行过程中所需要的额外的空间资源的量度。常用的空间复杂度的表示方法有O(1)、O(n)、O(n²)等。
例如，计算一个整数数组的总和，可以使用一个额外的变量来保存累加的结果，此时空间复杂度为O(1)。
再例如，对于一个长度为n的整数数组，如果创建一个相同长度的新数组来存储每个元素的平方，则空间复杂度为O(n)。
🔎3.度量
常见的对算法执行所需时间的度量：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)
上述的时间复杂度，经常考到，需要注意的是，时间复杂度是一个大概的规模表示，一般以循环次数表示，O(n)说明执行时间是n的正比，另外，log对数的时间复杂度一般在查找二叉树的算法中出现。渐进符号O表示一个渐进变化程度，实际变化必须小于等于O括号内的渐进变化程度。
🚀感谢：给读者的一封信
亲爱的读者，
我在这篇文章中投入了大量的心血和时间，希望为您提供有价值的内容。这篇文章包含了深入的研究和个人经验，我相信这些信息对您非常有帮助。
如果您觉得这篇文章对您有所帮助，我诚恳地请求您考虑赞赏1元钱的支持。这个金额不会对您的财务状况造成负担，但它会对我继续创作高质量的内容产生积极的影响。
我之所以写这篇文章，是因为我热爱分享有用的知识和见解。您的支持将帮助我继续这个使命，也鼓励我花更多的时间和精力创作更多有价值的内容。
如果您愿意支持我的创作，请扫描下面二维码，您的支持将不胜感激。同时，如果您有任何反馈或建议，也欢迎与我分享。
再次感谢您的阅读和支持！
最诚挚的问候， “愚公搬代码”
- 点赞
- 收藏
- 关注作者
评论（0）