数据结构与算法是计算机科学的基础，对于理解和优化程序性能至关重要。数据结构主要关注如何组织和存储数据，以便高效地访问和操作。算法则是解决问题或执行特定任务的精确步骤。
1. **数据结构**：
- **顺序查找**：在无序数据集中查找目标元素，时间复杂度通常为O(n)。
- **二分查找**：适用于有序数组，通过不断缩小搜索范围找到目标，时间复杂度为O(logn)。
- **分块查找**：将大数组分成小块，每块内部有序，提高查找效率。
- **B树和B+树**：适用于大量数据的磁盘存储，保持数据有序，支持高效的范围查询和插入操作。
2. **算法思想**：
- **时间复杂度**：衡量算法运行时间与输入数据量的关系，如O(1)、O(logn)、O(n)、O(nlogn)、O(n^k)、O(k^n)、O(n!)。
- **空间复杂度**：算法运行时所需的内存空间与输入数据量的关系。
3. **排序算法**：
- **归并排序**：稳定排序，分治策略，时间复杂度为O(nlogn)。Java的`Arrays.sort()`在特定条件下会选择归并排序。
- **快速排序**：快速且常用，平均时间复杂度为O(nlogn)，最坏情况O(n^2)。Java的`Arrays.sort()`在不同情况下会使用双轴快速排序。
- **插入排序**：简单排序，适合小规模或部分有序数据，最好情况O(n)。
- **TimSort**：Java的`Collections.sort()`默认使用，结合了稳定的归并排序和插入排序，适应多种数据输入。
4. **查找算法**：
- **静态查找**：查找表不发生变化，如顺序查找。
- **动态查找**：查找表允许插入和删除，如二叉树查找、平衡查找树（2-3树、红黑树）、B树和B+树。
- **无序查找**：对数据的顺序没有要求。
- **有序查找**：必须在有序数据中进行。
5. **蓄水池抽样**：
- **抽样方法**：在不确定规模的数据集中进行随机采样，保证每个元素被选中的概率相等。
- **步骤**：初始化大小为k的数组，随机替换或保留元素，直到遍历完整个数据集。
- **应用场景**：例如从字符流中进行随机采样，且不知道流何时结束。
这些基础知识构成了数据结构与算法的基础框架，掌握它们对于编写高效、可靠的程序至关重要。在实际编程中，选择合适的数据结构和算法可以显著提升程序性能，并降低复杂问题的解决难度。
评论0