【第一天】零基础入门刷题Python-算法篇-数据结构与算法的介绍（持续更新）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、Python数据结构与算法的详细介绍
- 1.基本概念
- 2.Python中的数据结构
- - 1. 列表（List）
  - 2. 元组（Tuple）
  - 3. 字典（Dictionary）
  - 4. 集合（Set）
  - 5. 字符串（String）
- 3.Python中的常用算法
- - 1. 排序算法
  - 2. 搜索算法
  - 3. 递归算法
  - 4. 动态规划
  - 5. 贪心算法
  - 6. 分治算法
  - 7. 回溯算法
  - 8. 图论算法
  - 9. 字符串算法
- 4.算法的时间复杂度和空间复杂度
- - 1. 时间复杂度
  - 2. 空间复杂度
总结

前言

提示：这里可以添加本文要记录的大概内容：

第一天Python数据结构与算法的详细介绍
第二天五种常见的排序算法
第三天两种常见的搜索算法
第四天两种常见的递归算法
第五天一种常见的动态规划算法
第六天一种常见的贪心算法

提示：以下是本篇文章正文内容，下面案例可供参考

一、Python数据结构与算法的详细介绍

1.基本概念

数据结构：是指计算机中存储和组织数据的方式。不同的数据结构适用于不同的应用场景，选择合适的数据结构可以显著提高程序的运行效率。数据结构涵盖数据内容、数据之间关系和数据操作方法，具有以下设计目标：

空间占用尽量少，以节省计算机内存。
数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。
提供简洁的数据表示和逻辑信息，以便算法高效运行。

算法：是指完成特定任务的一系列步骤或规则，它在有限时间内解决特定问题的一组指令或操作步骤。算法具有以下特性：

问题是明确的，包含清晰的输入和输出定义。
具有可行性，能够在有限步骤、时间和内存空间下完成。
各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同。

数据结构与算法高度相关、紧密结合，具体表现在以下三个方面：

数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。
算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。
算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。

2.Python中的数据结构

Python内置了多种数据结构，涵盖了常见的线性和非线性数据结构。以下是Python中一些主要的数据结构：

1. 列表（List）

列表（List）：Python中最常用的内置数据结构之一，可以存储任意类型的元素，并且支持动态调整大小。创建列表：my_list = []（空列表）或my_list = [1, 2, 3, 4, 5]（包含元素的列表）。
列表操作：添加元素my_list.append(6)、删除元素my_list.remove(3)、访问元素print(my_list[2])、列表切片print(my_list[1:4])。

2. 元组（Tuple）

元组（Tuple）：不可变的序列，创建后不能修改。元组通常用于存储固定数量的元素。创建元组：my_tuple = ()（空元组）或my_tuple = (1, 2, 3, 4, 5)（包含元素的元组）。
元组操作：访问元素print(my_tuple[2])、元组切片print(my_tuple[1:4])。

3. 字典（Dictionary）

字典（Dictionary）：键值对数据结构，支持快速查找、插入和删除操作。创建字典：my_dict = {}（空字典）或my_dict = {‘name’: ‘Alice’, ‘age’: 25, ‘city’: ‘New York’}（包含键值对的字典）。
字典操作：添加或更新键值对my_dict[‘age’] = 26、删除键值对del
my_dict[‘city’]、访问值print(my_dict[‘name’])、遍历字典for key, value in
my_dict.items(): print(f’{key}:{value}')。

4. 集合（Set）

集合（Set）：无序的、不可重复的数据结构，支持集合运算如交集、并集和差集。创建集合：my_set = set()（空集合）或my_set
= {1, 2, 3, 4, 5}（包含元素的集合）。集合操作：添加元素my_set.add(6)、删除元素my_set.remove(3)、集合运算（如并集my_set.union(other_set)、交集my_set.intersection(other_set)、差集my_set.difference(other_set)）。

5. 字符串（String）

字符串（String）：有序字符集合，支持多种字符串操作，如拼接、切片、查找等。
此外，Python还支持其他更复杂的数据结构，如栈（Stack）、队列（Queue）、树（Tree）、图（Graph）等。

3.Python中的常用算法

以下是Python中的一些常用算法：

1. 排序算法

排序算法：将一组数据按特定顺序排列。常见的排序算法有冒泡排序、选择排序、插入排序、快速排序和归并排序等。

冒泡排序：通过重复遍历要排序的数列，比较相邻元素的值，若发现逆序则交换，直到没有逆序为止。时间复杂度为O(n^2)，空间复杂度为O(1)。
选择排序：每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。时间复杂度O(n^2)，空间复杂度O(1)。
插入排序：将每个新元素插入到已排序部分的适当位置。时间复杂度O(n^2)（最坏情况），空间复杂度O(1)。
快速排序：选择一个基准元素，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，以达到整个数据变成有序序列。时间复杂度为O(n
log n)，空间复杂度为O(log n)（递归栈空间）。
归并排序：采用分治法，将数组分成两半，递归排序后合并。时间复杂度O(n log n)，空间复杂度O(n)（需要额外空间合并）。

2. 搜索算法

搜索算法：在数据集中查找特定元素。常见的搜索算法有线性搜索和二分搜索等。

线性搜索：从数据集的第一个元素开始，依次比较每个元素，直到找到目标元素或搜索完整个数据集为止。时间复杂度为O(n)，空间复杂度为O(1)。
二分搜索：要求数据集必须是有序的，通过不断将搜索范围减半来查找目标元素。时间复杂度为O(log n)，空间复杂度为O(1)。

3. 递归算法

递归算法：函数调用自身来解决问题的编程技巧。递归通常用于分治法、树和图的遍历等。

斐波那契数列：通过递归调用自身来计算斐波那契数列的第n项。时间复杂度为O(2^n)，空间复杂度为O(n)（递归栈空间）。
阶乘：通过递归调用自身来计算一个数的阶乘。时间复杂度为O(n)，空间复杂度为O(n)（递归栈空间）。

4. 动态规划

动态规划：解决最优化问题，通过将问题分解为子问题，并记录子问题的解以避免重复计算。时间复杂度和空间复杂度依具体问题而定，但通常较低于朴素递归解法。

5. 贪心算法

贪心算法：在每一步选择中都采取最好或最优（即最有利）的选择，从而希望能够导致结果是全局最好或最优的算法。时间复杂度依具体问题而定。

6. 分治算法

分治算法：
将问题划分为几个规模较小的子问题分别解决，然后将子问题的解合并得到原问题的解。快速排序和归并排序是分治算法的典型例子。

7. 回溯算法

回溯算法：通过搜索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃该解，即“回溯”并尝试另一个可能的候选解。时间复杂度通常很高，因为需要探索所有可能的解空间。

8. 图论算法

图论算法：

深度优先搜索（DFS）：
用途：用于图的遍历或路径查找。
时间复杂度：O(V+E)，其中V是顶点数，E是边数。
空间复杂度：O(V)（递归栈空间）。
广度优先搜索（BFS）：
用途：用于图的遍历或最短路径查找（无权图）。
时间复杂度：O(V+E)。
空间复杂度：O(V)（队列空间）。
Dijkstra算法：
用途：用于计算单源最短路径（有权图）。
时间复杂度：O(V^2)（朴素实现）或O((V+E) log V)（优先队列实现）。
空间复杂度：O(V)。
最小生成树算法：
Prim算法：
用途：用于求解最小生成树。
时间复杂度：
使用邻接矩阵：O(V^2)。
使用斐波那契堆等数据结构：O(E log V)。
空间复杂度：根据具体实现而定，通常与顶点数和边的数量相关。
Kruskal算法：
用途：用于求解最小生成树。
时间复杂度：O(E log E)，其中E是边的数量。
空间复杂度：O(E)（存储边）和O(V)（并查集数据结构）。
Floyd-Warshall算法：
用途：用于计算所有顶点对之间的最短路径（有权图）。
时间复杂度：O(V^3)，其中V是顶点数。注意这里的复杂度是立方，与上述算法不同。
空间复杂度：O(V^2)（存储距离矩阵）。