本文共 735 字，大约阅读时间需要 2 分钟。

一、时间复杂度

时间复杂度是衡量算法运行效率的重要指标。它反映了算法在处理问题时所需的运算量随问题规模变化的趋势。通常，问题规模用整数n表示，算法的时间复杂度可用函数f(n)表示为T(n)=O(f(n))，其中O表示渐近时间复杂度符号。

定义与概念

渐近时间复杂度的定义：如果存在两个正常数c和n0，使得对于所有n≥n0，f(n)≤c·g(n)，则f(n)=O(g(n))。这意味着随着问题规模n的增大，f(n)的增长率与g(n)一致。

时间复杂度的计算方法

常见渐进时间复杂度的对比：O(1) < O(log2n) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n)

二、空间复杂度

空间复杂度衡量算法运行过程中所占用的存储空间。它包括输入数据占用的空间、算法本身占用的空间以及辅助变量占用的空间。

定义与概念

算法的空间复杂度S(n)表示执行过程中所需存储空间的大小。与时间复杂度类似，若S(n)=O(g(n))，则表示随着问题规模n的增大，存储空间的增长率与g(n)一致。

空间复杂度的计算方法

通过分析输入数据和辅助变量的存储需求，可以评估算法的空间效率。