数据结构与算法（python）.pdf

### 数据结构与算法（Python） #### 核心知识点解析 ##### 一、算法效率与时间复杂度 **算法效率**是指算法完成特定任务所需资源（如时间或空间）的多少。在评估算法效率时，一个重要的概念是**时间复杂度**，它用来描述算法执行时间与输入数据规模之间的关系。 **时间复杂度**的概念引入了“大O记法”（Big O notation）。大O记法是一种数学符号，用于描述函数增长的上限。在算法分析中，我们通常关注的是算法的时间复杂度，特别是最坏情况下的时间复杂度（Worst-case time complexity）。 - **大O记法定义**：“对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)<=c*g(n)，就说函数g是f的一个渐近函数（忽略常数），记为f(n)=O(g(n))。” - **最坏时间复杂度**：表示算法完成工作最多需要多少基本操作，即在最不利的情况下算法的执行时间。 ##### 二、时间复杂度的计算规则 1. **基本操作**：只含有常数项的操作，其时间复杂度为O(1)。 2. **顺序结构**：多个操作顺序执行时，时间复杂度按加法计算。 3. **循环结构**：循环内的操作时间复杂度按乘法计算。 4. **分支结构**：分支结构的时间复杂度取其中最大的。 ##### 三、Python内置类型性能分析 - **List**：Python 中的列表提供了多种操作，不同操作的时间复杂度有所不同。例如，列表末尾添加元素的时间复杂度为O(1)，而插入或删除列表中间的元素的时间复杂度为O(n)。 - **Dict**：Python 中的字典提供了快速查找、插入和删除的功能，通常情况下，这些操作的时间复杂度为O(1)。 ##### 四、示例代码分析 在给定的部分内容中，通过两次尝试解决了寻找勾股数（满足a^2 + b^2 = c^2且a + b + c = 1000的正整数a、b、c）的问题。第一次尝试采用三层嵌套循环，时间复杂度为O(n^3)，执行效率较低；第二次尝试利用已知条件优化了搜索范围，时间复杂度降低至O(n^2)，大大提高了算法效率。 ```python # 第一次尝试 import time start_time = time.time() for a in range(0, 1001): for b in range(0, 1001): for c in range(0, 1001): if a**2 + b**2 == c**2 and a + b + c == 1000: print(f"a,b,c: {a},{b},{c}") end_time = time.time() print(f"elapsed: {end_time - start_time}") print("complete!") # 第二次尝试 import time start_time = time.time() for a in range(0, 1001): for b in range(0, 1001 - a): c = 1001 - a - b if a**2 + b**2 == c**2: print(f"a,b,c: {a},{b},{c}") end_time = time.time() print(f"elapsed: {end_time - start_time}") print("complete!") ``` 通过对比两次尝试的结果可以看出，优化后的算法不仅执行时间大幅减少，而且更容易理解和维护。 ##### 五、总结 本篇笔记重点介绍了数据结构与算法的基础概念，特别是时间复杂度及其计算方法。通过对Python内置类型性能的分析，以及具体示例代码的展示，加深了对算法效率的理解。在实际编程中，合理选择数据结构和优化算法是非常重要的，能够显著提高程序的运行效率。