墨尔本大学 COMP90038 Algorithms and complexity 学习笔记

【算法与复杂性】在计算机科学中，算法是解决问题的核心工具，而复杂性则是衡量算法效率的重要标准。墨尔本大学的COMP90038课程深入探讨了这两个主题，旨在帮助学生掌握高级的算法设计和分析技巧。 **概念** 1. **Algorithmic Problems**：算法问题通常涉及在有限步骤内解决特定计算任务。这些问题可以是数学问题、数据处理任务或其他形式的决策问题。学习如何将现实世界的问题转化为可执行的算法是这个课程的基础。 2. **Algorithm**：一个算法是一系列明确的步骤，用于解决特定问题或完成特定任务。它必须是确定性的，有限的，并且能在有限的时间内终止。理解算法的基本结构和设计原则是这门课程的重点。 3. **时间复杂度**：时间复杂度是评估算法运行时间随着输入规模增加而增长的速度。它提供了算法效率的理论上限，常用的表示方法有大O记号。 4. **增长次数表**：用于比较不同算法的增长速率，例如线性（O(n)）、对数（O(log n)）、平方（O(n²)）和指数（O(2^n)）等。理解这些增长模式对于选择最佳算法至关重要。 5. **渐进符号**：包括大O、Ω和Θ记号，它们分别表示算法运行时间的上限、下限和精确界限，帮助我们理解和描述算法的最坏、最好和平均性能。 **小总结** - **基本操作与输入规模度量**：分析算法时，关注基本操作的数量（如比较、赋值）以及输入规模（如问题实例的大小n）对算法运行时间的影响。 **Master Theorem** 6. **Master Theorem** 是一种解决递归关系T(n) = aT(n/b) + f(n)的工具，其中a和b为常数，f(n)是关于n的函数。这个定理为解决分治算法的时间复杂度提供了一种直接的方法。 7. **Euclid’s Algorithm**：欧几里得算法是求解最大公约数（GCD）的经典算法，基于“较大的数除以较小的数，再用除数去除余数”的递归过程。其时间复杂度可以用Master Theorem来分析。 **递归（Recursion）** 8. **Recursion** 是算法设计的一种强大工具，通过函数调用自身来解决问题。理解递归的原理，包括基线条件（base case）和递归情况（recursive case），以及如何避免无限循环，是学习算法的重要部分。 **数据结构** 9. **数组（array）**：是最基础的数据结构，提供随机访问但插入和删除操作相对较慢。理解数组的特性对于设计和分析算法至关重要。 10. **链表（linked list）**：链表允许动态地添加和删除元素，但不支持随机访问。链表分为单链表、双链表和循环链表等类型，各有优缺点，适合不同场景。 以上只是课程的冰山一角，COMP90038还涵盖了树、图、排序算法、查找算法、动态规划、贪心算法、随机化算法等多个主题，旨在培养学生的算法思维和复杂性分析能力，以应对不断发展的信息技术挑战。通过这门课程的学习，学生能够掌握解决复杂问题的高效方法，为未来在IT领域的职业生涯打下坚实基础。