时间复杂度是算法运行所需的时间量度,通常用大 O 表示,表示算法执行步骤数目与输入规模之间的关系。时间复杂度描述了算法运行时间随着输入规模增长时的增长趋势。
空间复杂度是算法在运行过程中所需的存储空间量度,同样用大 O 表示,表示算法运行所需的额外存储空间与输入规模之间的关系。空间复杂度描述了算法运行所需的额外存储空间随着输入规模增长时的增长趋势。
"时间换空间"和"空间换时间"是指在设计算法时,可以根据具体情况选择使用更多的时间来节省空间,或者使用更多的空间来节省时间。以下是一些时间换空间和空间换时间的例子:
- 时间换空间:缓存技术就是典型的时间换空间策略。通过将计算结果缓存起来,下次再遇到相同输入时可以直接返回缓存的结果,省去重复计算时间,但需要占用额外的空间存储缓存结果。
- 空间换时间:排序算法中的归并排序和快速排序,虽然时间复杂度较低,但需要额外的空间来存储中间结果,属于典型的空间换时间策略。
- 时间换空间:动态规划算法中常使用时间换空间策略,通过保存中间计算结果来避免重复计算,提高算法效率。
- 空间换时间:哈希表(Hash Table)是一种典型的空间换时间的数据结构,通过消耗额外的空间来实现常量级别的查找、插入和删除操作。