算法学习

在这里，汇集了搜索算法，包括线性查找、二分查找等。 线性查找（Linear Search） 代码实现 #include <iostream> using namespace std; int main() { int nums[10]; for (int i = 0; i < 10; i++) { nums[i] = i + 1; // 初始化数组，1~10 } int find; cin >> find; // 线性查找 for (int i = 0; i < 10; i++) { if (nums[i] == find) { cout << i; // 输出找到的索引 return 0; } } cout << "Not found"; // 没找到 } 算法解析 这是最基本的查找算法，也是最简单的一种。 遍历数组 for (int i = 0; i < 10; i++)，依次检查 nums[i] 判断是否匹配 if (nums[i] == find)，如果找到目标值，就输出索引 i 提前返回 return 0; 避免多余的遍历，提高效率 未找到时输出 “Not found” 遍历结束仍然没找到目标值，则打印 “Not found” 时间复杂度为 O(n)，适用于无序数组，或小规模数据 二分查找（Binary Search） 代码实现 #include<iostream> using namespace std; int main() { int nums[10]; for (int i = 0; i <= 9; i++) { nums[i] = i + 1; } int find = 0; // 要查找的元素 int left = 0, right = 9; // 元素下标 int mid = 0; // 元素下标 cin >> find; while (left <= right) { mid = (left + right) / 2; if (nums[mid] > find) { // 要找的元素在中点左边 right = mid - 1; continue; } if (nums[mid] < find) { //要找的元素在中点左边 left = mid + 1; continue; } if (nums[mid] == find) { cout << mid; return 0; } } cout << "Not found"; } 算法解析 初始化 nums 数组被初始化为 {1, 2, 3, …, 10}，即 升序排列。 left = 0, right = 9，分别表示搜索范围的 左端 和 右端。 mid = (left + right) / 2，计算当前范围的 中间元素。 查找过程 如果 nums[mid] > find，说明目标在 左半部分，所以更新 right = mid - 1。 如果 nums[mid] < find，说明目标在 右半部分，所以更新 left = mid + 1。 如果 nums[mid] == find，找到目标，输出索引并终止程序。 终止条件 找到目标时，输出其索引并返回。 若 left > right，表示搜索范围为空，目标元素不存在，输出 “Not found”。 时间复杂度 二分查找的时间复杂度是 O(log N)，原因是： ...

当我们提到算法复杂度时，可以把它当作衡量完成一项任务效率的标准。想象你和朋友一起比赛，看谁能更快地完成整理书架的任务。你们有两种不同的做法，最终谁更快完成任务，谁就是胜利者。通过算法复杂度，我们能够评估不同方法在完成任务时的效率，帮助我们在各种情况下选择最佳的方案。 时间复杂度：任务做得有多快？ 时间复杂度就像是完成任务所需要的时间。假设你有100本书要整理，每次拿一本书，你都需要检查它放对了没，直到所有书都摆放好了。那么，整理书架的时间就跟书的数量成正比。 在计算机科学中，算法的时间复杂度通过大O符号表示，用来描述算法的运行时间随输入值大小的变化趋势。它通常忽略低阶项和系数，只关注输入规模趋近无穷时的表现。时间复杂度常用来衡量算法在最坏情况下的执行时间，也可用来分析平均情况。通过估算算法操作单元的数量来计算时间复杂度，常见的分类包括线性时间算法（O(n)）和指数时间算法（O(Mn)）。（总结自Wikipedia） 常见的时间复杂度 O(1) — 常数时间复杂度 如果不管有多少本书，任务所需时间都一样（比如，找几本书），这就是常数时间复杂度。就像你每次做的动作都很简单，任务的大小对时间没有太大影响。 O(n) — 线性时间复杂度 假设你是一本一本地整理书，每增加一本书，整理的时间就多一点。这就是线性时间复杂度，任务量增加，所需时间也按比例增加。 O(n²) — 平方时间复杂度 如果你需要比别人做得更复杂，比如检查每本书与其他每本书的位置是否匹配，时间就会随着任务数量的增加加速增加。每本书要和其他所有书比对一次，这就是平方时间复杂度。 O(log n) — 对数时间复杂度 这种复杂度表示每次操作都会将问题规模缩小一半，导致时间增长相对较慢。比如，二分查找就是这种算法类型，每次将搜索范围减半，大大提升了效率。 O(n log n) — 对数线性时间复杂度 这种复杂度常见于高效的排序算法，比如快速排序和归并排序。它的时间复杂度优于O(n²)，但没有O(n)那样直接。 空间复杂度：做任务需要多少空间？ 空间复杂度就像是你整理书架时需要的额外空间。假设你有一张大桌子用来暂时放书，那么空间复杂度就是你需要多少桌子来摆放这些书。 在计算机科学中，空间复杂度描述了一个算法或程序执行时所需的存储空间大小，通常以输入值长度为函数。类似于时间复杂度，空间复杂度也使用大O符号表示，如 O(n)、O(n log n)、O(2^n) 等，其中n代表输入长度，影响算法的空间需求。空间复杂度计算时不考虑算法的执行时间。（总结自Wikipedia） 常见的空间复杂度 O(1) — 常数空间复杂度 如果你只需要一个小桌子就能完成任务，不管书有多少，空间需求都一样。这就是常数空间复杂度，表示你对空间的需求是固定的，不会随任务大小变化。 O(n) — 线性空间复杂度 如果你需要一张桌子来放每一本书，那么空间复杂度就是线性的。随着书的增多，你需要的空间也会增加。 生活中的例子： O(1)：找固定的物品（比如桌子上的一支笔），不管桌子多大，时间都差不多。 O(n)：检查书包里的所有物品，时间随着物品数量的增加而增加。 O(n²)：如果你需要检查每两件物品之间的匹配情况，随着物品数量增加，任务变得更加复杂。 大O符号 在算法分析中，我们使用大O符号来描述算法的时间或空间复杂度，特别是在最坏情况下。它帮助我们理解数据量增大时，算法性能会如何变化。通过大O符号，我们可以评估不同算法在处理大数据时的效率。 大O符号（Big-O notation）是用来描述算法时间复杂度或空间复杂度的数学符号，表示随着输入数据规模增大，算法的性能或资源需求的增长趋势。大O符号关注的是输入规模趋近无穷时算法的增长速率，忽略常数因子和低阶项，旨在提供算法在最坏情况下的表现。常见的时间复杂度有O(1)（常数时间）、O(n)（线性时间）、O(n²)（平方时间）等，它们帮助我们评估不同算法的效率和适应性，尤其在处理大数据时。（来源：ChatGPT） 时间复杂度分析 O(1)：常数时间复杂度，执行时间不随输入规模的变化而变化。 O(n)：线性时间复杂度，时间随输入规模成正比增加。 O(n²)：平方时间复杂度，时间随输入规模的平方增长，常见于双重循环。 O(log n)：对数时间复杂度，时间增长较慢，常用于二分查找、平衡树等算法。 O(n log n)：对数线性时间复杂度，通常出现在高效排序算法中，如快速排序、归并排序等。 空间复杂度分析 O(1)：常数空间复杂度，额外的空间需求不随输入规模的变化而变化。 O(n)：线性空间复杂度，额外空间需求与输入规模成正比。 总结 & 共勉 希望通过这个简洁的介绍，你对算法复杂度有了更加清晰的理解。如果你有任何问题或想深入探讨某个算法复杂度，随时欢迎提问！ ...

算法 算法定义 算法（algorithm）是指在有限时间内通过一组明确的步骤或指令来解决特定问题的过程。它具有以下基本特性： 明确性：问题及其输入输出是清晰定义的，确保在不同的执行环境下可以得到一致的结果。 可行性：算法能够在有限的步骤、时间和内存空间内完成，保证其可以在实际系统中执行。 确定性：每个步骤有清晰的定义，并且在相同的输入和运行条件下，算法的输出始终一致，避免了不确定性和随机性。 最优性：在满足问题要求的前提下，算法能够实现最高效的执行，例如最短的时间复杂度和最少的空间消耗。 实例： 排序算法，如冒泡排序（Bubble Sort）和快速排序（Quick Sort），用于将一组无序数据排列为有序数据。快速排序通常被认为是最优的，因为它的平均时间复杂度是 O(n log n)，而冒泡排序的时间复杂度是 O(n²)。 算法复杂度 算法复杂度（algorithm complexity）是用来衡量算法执行效率的指标，主要包括时间复杂度和空间复杂度。它反映了算法执行时所需资源的消耗，通常用于评估算法的优劣。 时间复杂度：描述算法执行所需时间的增长情况，通常使用大 O 表示法（Big-O notation）。例如，O(n)、O(log n)、O(n²) 等表示算法随着输入规模的增加，运行时间是如何变化的。 空间复杂度：描述算法执行时所需内存空间的增长情况。与时间复杂度类似，空间复杂度也可以用大 O 表示法来表示。 常见的时间复杂度： O(1)：常数时间复杂度，表示算法的执行时间不随输入规模的增加而变化。 O(log n)：对数时间复杂度，表示算法的执行时间随着输入规模的增加而缓慢增长。例如，二分查找算法。 O(n)：线性时间复杂度，表示算法的执行时间与输入规模成正比。 O(n²)：平方时间复杂度，表示算法的执行时间随着输入规模的平方增长。例如，冒泡排序、插入排序等。 O(n log n)：对数线性时间复杂度，表示算法的执行时间比线性增长快，但比平方增长慢。例如，快速排序和归并排序。 这一部分内容将在第二章细讲 实例： 在查找某个元素时，线性查找（O(n)）的时间复杂度较高，适用于小规模数据。而二分查找（O(log n)）则适用于已经排序好的数据，效率要高得多。 数据结构 数据结构定义 数据结构（data structure）是指组织和存储数据的方式，它涉及数据内容、数据间的关系以及对数据的操作方法。良好的数据结构设计能够有效提高程序的性能，达到高效处理数据的目的。数据结构的设计目标包括： 空间效率：尽量减少内存占用，节省计算机资源。 操作效率：使数据的访问、插入、删除、更新等操作尽可能快速，提升算法的执行效率。 简洁性：提供简洁且直观的数据表示和逻辑结构，以便算法能高效运行。 平衡性：数据结构的设计是一个权衡过程，为了在某一方面取得优化，往往需要在其他方面做出妥协。例如，哈希表能够提供快速的查找操作，但它的空间消耗可能较大。 常见的数据结构： 线性结构：如数组、链表、栈、队列。 树形结构：如二叉树、平衡二叉树、B 树。 图形结构：如无向图、有向图、加权图。 哈希结构：哈希表用于快速查找。 数据结构与算法的关系 数据结构与算法是紧密相关的，它们的结合体现在以下几个方面： 数据结构是算法的基础：数据结构为算法提供了有序的存储结构和方法，通过结构化的存储方式组织数据，并为算法提供快速的访问和修改操作。例如，数组和链表是最常见的数据结构，分别适合不同的算法需求。 算法为数据结构赋予功能：数据结构本身仅存储数据，只有与算法结合，才能发挥其应有的作用。通过不同的算法，可以对同一数据结构进行各种操作，如排序、查找、遍历等。 数据结构的选择影响算法的效率：同一问题可以通过不同的数据结构来实现，选择合适的数据结构能够显著提高算法的效率。例如，图的遍历可以通过邻接矩阵或邻接表实现，选择不同的数据结构会影响算法的性能。 实例： 在实现图的最短路径算法时，使用邻接矩阵的空间复杂度较高，但适合密集图；而使用邻接表则适用于稀疏图，能够节省内存并提高效率。 在实现深度优先搜索（DFS）时，栈（Stack）是一个重要的辅助数据结构，它能够帮助我们跟踪节点的遍历路径。 总结 数据结构与算法是计算机科学的核心，良好的数据结构设计能够帮助我们高效地存储和操作数据，而合理选择和优化算法可以显著提高程序的性能。理解它们之间的关系，能够帮助我们在实际编程中做出更合适的选择，提高代码的执行效率和可维护性。

欢迎来到我的《算法自学笔记》专栏！这是我在自学算法过程中的一个学习日志，旨在记录并分享我对常见算法和数据结构的理解、学习过程中的思考以及探索到的有用资源。我希望通过这个专栏，能帮助自己更好地总结学习成果，同时为其他对算法感兴趣的同学提供一些启发和参考。 专栏内容概览 本专栏将涵盖以下几个主要方面： 基本数据结构：包括数组、链表、栈、队列、哈希表、树、图等常见数据结构。 排序与查找算法：涉及快速排序、归并排序、二分查找、线性查找等常用算法。 动态规划：深入讲解背包问题、最短路径问题、最长公共子序列等经典问题的解法。 图算法：介绍深度优先搜索、广度优先搜索、最小生成树、最短路径等图相关算法。 其他算法：包括贪心算法、回溯算法、分治算法等常见的高级算法。 专栏目标 整理学习笔记：将学习过程中遇到的关键点、算法实现和常见问题进行总结，并加以归纳整理。 分享学习经验：记录并分享自己的自学心得，帮助更多对算法感兴趣的学习者更高效地入门和进阶。 持续更新：随着学习的深入，我将持续更新专栏内容，不断补充新的算法和数据结构，力求使本专栏内容更加丰富和完善。 专栏发展方向 目前，我已完成了常见数据结构和部分经典算法的学习笔记。未来，我会继续扩展更深入的算法和数据结构内容，并根据实践经验不断优化和完善笔记。 此外，专栏的配套网站也在开发中，未来将提供更加直观的学习资料，并结合在线编程和算法演示，进一步增强互动性和学习体验。 如何使用本专栏 仓库地址 浏览笔记：可以随时浏览并参考专栏中的各类学习笔记，帮助你理解算法的核心思想及其实现方式。 贡献代码：如果你在某个算法或数据结构上有新的见解或改进，欢迎通过提交 Pull Request 参与贡献。 参与讨论：如果你在学习过程中有问题或想法，可以在 Issues 区域提出，我们一起讨论、解决。 关于我 我的背景 我是一个初二学生，虽然算法学习起步较晚，但我一直对编程和算法充满浓厚兴趣。如今，我正通过自学不断提升自己的算法水平，并希望能通过实践提升自己的编程能力。 为什么专注算法学习 在我的学习经历中，我曾对编程语言产生浓厚兴趣，并开始尝试学习一些编程语言。然而，老师建议我先专注于算法学习，因为掌握算法的核心思维将帮助我更好地理解编程语言的底层原理。因此，我决定将语言学习暂时搁置，集中精力攻克算法，培养扎实的逻辑思维能力。这一决定，也为我后续的编程之路打下了坚实的基础。 我的目标 我的目标是通过不断学习算法和数据结构，在信息奥赛（NOI）中争取获得省赛一等奖。我相信，通过扎实的算法基础，不仅能提升我的编程水平，也能帮助我在将来的编程竞赛中脱颖而出。 学习资源与参考资料 在这条自学算法的道路上，我参考了以下书籍和资料： 《hello 算法》：为初学者提供了很多实用的算法学习资料和代码示例，帮助我从零基础入门。 CS自学指南：为自学计算机科学的学生提供了清晰的学习路径，帮助我规划和组织学习内容。 HackWay技术学习路线：提供了从入门到进阶的技术学习路线，帮助我更系统地提升技能。 《算法基础：打开算法之门》：为算法入门提供了详细的讲解，帮助我理解基础概念。 《算法导论》：经典教材，深入探讨了算法设计和分析，是我的重要参考书。 《数据结构、算法与应用：C++语言描述》：结合C++语言讲解数据结构和算法的实现，帮助我理解实际应用。 许可证 此专栏内容采用 CC BY-NC-SA 4.0 许可证，您可以在非商业用途下使用和分享本专栏的内容，但需要注明出处，并且分享的内容须遵循相同的许可协议。 致谢 特别感谢所有在算法和编程领域做出贡献的前辈，正是因为有了他们的知识和经验，我们这些自学者才能更容易获得进步。希望通过我的努力，这些宝贵的知识能帮助更多的学习者。 这是我自学算法过程中的一个小小总结和记录，希望你在这个专栏中能收获知识与灵感。欢迎你在学习中提出建议，或者与我共同探讨算法的奥妙！