算法导论 | Tools - Wyatt's Notes

算法是解决问题的配方: 算法就像烹饪食谱, 它告诉你要做什么步骤、按什么顺序、什么时候停止。好的算法（食谱）让你更快地得到结果（解决方案），尤其是在处理大量数据（为一大群人做饭）时。

为什么重要: 算法决定了一个问题是在几秒内解决还是需要几个世纪。选择正确的算法可以把一个不可处理的问题变成日常任务。

关键洞察: 效率是关于增长率的，而不是绝对速度, 理解运行时间如何随输入规模增长，让你能够预测从未见过的问题的性能。

算法是有限条明确定义的指令序列，接受输入并产生输出。这个定义看似简单。实际上，“产生正确答案的算法”和”产生正确答案且足够快以产生实际价值的算法”之间的差距，正是大部分工程工作发生的地方。

你构建、维护或调试的每个系统都是算法的组合：数据库用于服务查询的 B 树索引、TCP 中决定服务发送数据速度的拥塞控制算法、将请求分配到集群的负载均衡算法、运行时中回收内存的垃圾收集器。在深层次理解这些算法，是能够诊断延迟回归的工程师与只能重启服务的工程师之间的区别。

数据结构和算法密不可分。数据结构是组织内存中数据的特定方式；算法是对该数据执行操作的序列。选择错误的数据结构会使最好的算法变慢，而选择正确的数据结构可以使朴素算法足够快。

复杂度分析是评估算法效率的数学框架。它不关心具体的运行时间（这取决于硬件、语言和输入分布），而是关心当输入增长时，资源消耗如何增长。

时间复杂度用大 O 符号表示算法在最坏情况下的运行时间增长率：

空间复杂度衡量算法在执行过程中使用的额外内存：

连续内存存储，支持 $O(1)$ 随机访问，$O(n)$ 插入/删除。

非连续内存存储，支持 $O(1)$ 插入/删除（给定位置），$O(n)$ 随机访问。

后进先出 (LIFO) 抽象数据类型。支持 $O(1)$ 的 push 和 pop 操作。

先进先出 (FIFO) 抽象数据类型。支持 $O(1)$ 的入队和出队操作。

通过哈希函数将键映射到数组索引。平均 $O(1)$ 查找、插入和删除。

1. 给定一个未排序数组，设计 $O(n)$ 时间复杂度的算法找到两个数之和等于目标值。
2. 实现一个支持 $O(1)$ 最小值查询的栈。
3. 比较数组和链表在不同操作下的性能特征。

This introduction provides comprehensive coverage of Zh content for the Tools qualification, with detailed explanations, worked examples, and practice questions aligned to the specification.

This page includes:

• Key Definitions: Precise explanations of essential concepts
• Core Concepts: Detailed treatment of fundamental principles
• Worked Examples: Step-by-step solutions demonstrating application
• Practice Questions: Examination-style questions with mark schemes
• Common Pitfalls: Frequent errors and how to avoid them
• Exam Tips: Strategies for maximising marks

1. Read through the introductory material to establish context
2. Study the definitions and core concepts carefully
3. Work through the worked examples, following each step
4. Attempt the practice questions independently
5. Review your answers against the provided solutions
6. Note any areas requiring further revision

• Foundational definitions and terminology
• Application of principles to examination contexts
• Connections to related topics within the specification
• Assessment objective alignment

• Active Recall: Test yourself on the material rather than passively re-reading
• Spaced Repetition: Review this content at increasing intervals
• Interleaving: Mix this topic with others during study sessions
• Elaborative Interrogation: Ask yourself why each concept works

Practise applying these concepts under timed conditions. Focus on understanding what each question is asking and how marks are allocated. Review examiner reports to learn from common mistakes made by other students.

• Flashcards for rapid revision of key terms
• Diagnostic tests to identify remaining gaps
• Practice problems with detailed worked solutions
• Cross-references to related topics

• Algorithms
• Introduction to Algorithms
• Introduction to General Notes

This section provides detailed coverage of advanced concepts, including full derivations, proofs, and extended examples.

Complete mathematical derivations and proofs are provided where appropriate. Each step is explained to ensure understanding of the underlying reasoning.

Advanced examples demonstrate the application of concepts to complex problems. These examples go beyond standard exam questions to develop deeper understanding.

This material connects to current research and advanced applications in the field. Understanding these connections provides context for the study material.

Ensure you have mastered the prerequisite material before attempting this advanced content.