算法的时间复杂度与内存复杂度的定义是什么？

核心定义 #

时间复杂度 #

时间复杂度是衡量算法运行效率的核心指标，它不会绑定具体硬件、编译器、运行环境来计算实际耗时，而是仅关注算法执行操作的数量随输入规模增长的变化趋势，通常用大O符号O()来表示。
比如你要遍历长度为n的数组，每个元素都要访问一次，操作数和n完全成正比，时间复杂度就是O(n)；如果是两层嵌套循环遍历n*n的二维数组，复杂度就是O(n²)。

内存复杂度（也叫空间复杂度） #

内存复杂度用来衡量算法运行时额外占用的存储空间随输入规模的变化趋势，同样用大O符号O()统计。注意这里统计的是除了输入数据本身占用的空间之外，算法运行需要用到的临时变量、额外数据结构、递归调用栈等的空间变化规律。
比如遍历数组时你只用到1个临时计数变量，额外占用的空间不会随n的增长变多，内存复杂度就是O(1)，这类算法也叫原地算法；如果你需要额外开一个长度和输入一致的数组存计算结果，内存复杂度就是O(n)。

通用分析规则 #

不管是什么类型的算法，分析复杂度都可以遵循以下通用规则：

• 只保留最高阶项，忽略常数、低阶项：如果统计出来的操作数是5n² + 3n + 10，最终的复杂度只取最高阶的n²，也就是O(n²)。因为当输入规模n足够大时，低阶项和常数对整体规模的影响可以完全忽略，不会改变增长趋势。
• 常见复杂度的优先级（运行效率从高到低/内存占用从少到多）：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)。其中O(2ⁿ)及以上的指数级、阶乘级复杂度仅适合极小输入规模的场景，生产环境几乎不会使用。
• 复杂度的三种场景区分：

  没有特殊说明的情况下，行业内默认说的复杂度指最坏时间复杂度，也就是输入处于最不利场景下的复杂度，用来保证算法的性能下限。比如快速排序最坏复杂度是O(n²)，但平均复杂度是O(n log n)，因为最坏场景出现概率极低，日常我们也会默认说快排的复杂度是O(n log n)。

• 递归算法的分析方法：时间复杂度=递归调用总次数 * 单次递归的操作数；内存复杂度=递归的最大深度 * 每层递归额外占用的空间，递归调用栈的空间必须统计在内。
• 所有基础操作默认是O(1)：算术运算、逻辑判断、变量赋值、数组按索引取值、哈希表按键取值等操作，执行耗时都是固定的，不会随输入规模变化，分析时可以直接按单次操作计数。

常见认知误区 #

• 代码行数和复杂度没有直接关系：几十行的递归代码复杂度可能高达O(2ⁿ)，上百行的线性遍历代码复杂度也可能只是O(n)。
• 复杂度高低不直接等于小输入规模下的实际运行速度：O(1)的算法如果内部有大量常数操作，n很小的时候实际运行速度可能比O(n)的算法更慢，只有输入规模足够大时，复杂度的增长趋势优势才会体现出来。
• 输入本身的空间不算内存复杂度：比如输入是长度为n的数组，这部分空间是输入自带的，不需要统计到内存复杂度里，只有算法运行时额外申请的空间才需要统计。

内容的提问来源于stack exchange，提问作者Rohit