数据结构与算法
程序 = 数据结构 + 算法
在计算机科学中，程序的设计和实现离不开两个核心概念：数据结构和算法。数据结构定义了数据的存储和组织方式，而算法则提供了解决问题的步骤和方法。
算法介绍
概述
算法是解决特定问题的一系列明确指令的集合，通常表示为易于理解的计算机程序的步骤。算法具有五个基本特征：
- 独立性：算法是解决问题的思想，不依赖于具体的编程语言。
- 有输入：算法需要接收输入数据。
- 有输出：算法处理完输入数据后，会产生输出结果。
- 有穷性：算法必须在有限步骤内完成。
- 确定性：算法的每一步骤都是明确且唯一的。
- 执行性：算法中的每一步都是可执行的。
如何衡量算法的优劣
算法的优劣主要通过两个维度来衡量：时间复杂度和空间复杂度。
- 时间复杂度：表示算法执行时间随问题规模增长而变化的趋势，采用大O标记法表示。只考虑主要条件，忽略次要条件。
- 空间复杂度：表示算法执行过程中临时占用空间的大小，同样采用大O标记法表示。
时间复杂度介绍
- 概述：时间复杂度反映了算法的效率，表示算法随着问题规模的变化而表现出来的趋势。
- 计算规则：只考虑主要条件，忽略次要条件。
- 基本运算：
- O(1)：常数时间复杂度，执行时间不随问题规模变化。
- O(n)：线性时间复杂度，执行时间与问题规模成正比。
- O(n²)、O(n³)：平方阶、立方阶时间复杂度，执行时间随问题规模增长迅速。
- O(logn)、O(nlogn)：对数阶、线性对数阶时间复杂度，执行时间增长相对较慢。
最优、最坏和平均时间复杂度
- 最优时间复杂度：通常无实际意义，表示算法在最佳情况下的执行时间。
- 最坏时间复杂度：算法的一种保证，表示在任何情况下算法执行所需的最大步骤数。
- 平均时间复杂度：算法在一定操作次数内的趋势走向。
常见的时间复杂度
- O(1)
- O(logn)
- O(n)
- O(nlogn)
- O(n²)
- O(n³)
空间复杂度
空间复杂度表示算法执行过程中临时占用空间的大小，也用大O标记法表示。常见的空间复杂度从低到高依次为：O(1) < O(logn) < O(n) < O(n²) < O(n³)。
时空转换
时空转换是一种开发思想，即在算法设计中权衡时间和空间的使用。有时为了节省时间，可能需要增加空间的使用；反之亦然。
实操
排序类算法
- 冒泡排序
- 原理：相邻元素两两比较，大的往后走，直至所有元素排序成功。
- 时间复杂度：最优O(n)，最坏O(n²)。
- 稳定性：稳定排序算法。
- 选择排序
- 原理：每轮找到该轮的最小值，放到最小索引处，直至所有元素排序成功。
- 时间复杂度：最优和最坏均为O(n²)。
- 稳定性：不稳定排序算法。
- 插入排序
- 原理：将列表分为排好序和待排序两部分，每次从未排序部分取出一个元素，与已排序部分比较并插入到合适位置。
- 时间复杂度：最优O(n)，最坏O(n²)。
- 稳定性：稳定排序算法。
查找类算法
- 二分查找
- 概述：高效率的查找算法，要求被查找的列表必须是有序的。
- 原理：通过不断缩小查找范围来找到目标元素。
- 时间复杂度：最优O(1)，最坏O(logn)。
数据结构介绍
概述
数据结构是存储和组织数据的方式，决定了数据的存储效率和访问方式。
分类
- 线性结构
- 特点：每个节点都只有一个前驱节点和一个后继节点。
- 举例：列表、栈、队列、链表。
- 顺序表
- 特点：采用连续的内存空间来存储数据。
- 扩容策略：每次扩容增加固定数目或容量翻倍。
- 增删操作：末尾增删时间复杂度O(1)，中间增删（保序）时间复杂度O(n)。
- 链表
- 特点：非连续空间存储数据，由节点组成，每个节点包含数值域和地址域。
- 分类：单向链表、单向循环链表、双向链表、双向循环链表。
- 非线性结构
- 特点：每个节点可以有多个前驱节点和多个后继节点。
- 举例：树、图。
- 树状结构
- 特点：有且只有一个根节点，每个节点可以有多个子节点（除根节点外）。
- 分类：完全二叉树、满二叉树、不完全二叉树。
- 遍历方式：深度优先（前序、中序、后序）和广度优先。
通过深入理解数据结构和算法，可以更有效地设计和实现高效的计算机程序。