20.离散化
离散化
离散化是一种将无限空间中的有限个体映射到有限空间中的方法,常用于处理数据范围很大但实际数据量较小的问题。
在线性表章节已了解二分查找的基本原理,当一个问题的答案具有单调性时——即随着答案的增大或减小,判定条件的结果也呈现单调变化,比如答案越大条件越容易满足,或者答案越小条件越容易满足,可以通过二分查找,在过程中根据判定条件是否满足来调整二分的方向逼近解的过程。
本章探讨了算法分析的核心概念,通过求解最大连续和问题展示了不同算法设计策略的效率差异,并引入了复杂性理论、分治法以及它们在优化算法时间复杂度上的应用。从简单的枚举方法到高效的动态规划与分治策略,逐步揭示了解决问题时算法选择的重要性及其对计算资源消耗的深远影响。
通过编程模拟生活中的活动、现象,是解决各种问题的基础。很多问题并不需要特定的算法去解决,往往有效利用各种数据类型,根据问题的背景建模为数据的表达,按部就班地操作,就可以得到答案。
超出 long long (\(2^64\)) 范围的数字的加减乘除就是一类典型的模拟,称为高精度问题。
本章介绍图的基本概念、存储方式以及两种基本图搜索算法——深度优先搜索(DFS)和广度优先搜索(BFS),涵盖图的定义、分类、存储结构及其在代码中的实现,并提供DFS和BFS的典型模板代码。