时间空间复杂度入门
对于初学者，你只需要记住以下几点：
1、时空复杂度用 Big O 表示法表示（类似O(1), O(n²), O(logn) 等）。它们都是估计值，不需要精确计算，且仅保留最高增长项。
比方说 O(2n²+3n+1)等同于 O(n²)O(n²)，O(1000n+1000) 等同于 O(n)O(n)。
2、我们分析算法的复杂度时，一般分析的是最坏情况的复杂度。它们都是越小越好。比方说时间复杂度 O(n)的算法比 O(n²)的算法执行效率高，空间复杂度 O(1)的算法比 O(n)的算法内存消耗小。
当然，一般我们要说明这个 n 代表什么，比如 n 代表输入的数组的长度。
4、如何估算？现在你可以简单理解：时间复杂度大部分情况下就是看 for 循环的最大嵌套层数；空间复杂度就看算法申请了多少空间来存储数据。
注意
以上的分析方法中，有些细节并不严谨：
1、按照 for 循环的嵌套层数来估算时间复杂度是简化的方法，其实不完全准确。
2、大部分时候我们是分析最坏情况下的复杂度，但是对于数据结构 API 的复杂度衡量，我们会分析平均复杂度。
举几个例子来说比较直观。
时间/空间复杂度案例分析
示例一，时间复杂度 O(n)，空间复杂度 O(1)：
算法包含一个 for 循环遍历 nums 数组，所以时间复杂度是 O(n)，其中 n 代表 nums 数组的长度。我们的算法只使用了一个 sum 变量，这个 nums 是题目给的输入，不算在我们算法的空间复杂度里面，所以空间复杂度是 O(1)。
示例二，时间复杂度 O(n)，空间复杂度 O(1)：
其实只有当 n 是 10 的倍数时，算法才会执行 for 循环，时间复杂度是 O(n)。其他情况下算法会直接返回，时间复杂度是 O(1)。但是算法复杂度只考察最坏情况，所以这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。
示例三，时间复杂度 O(n²)，空间复杂度 O(1)：
Java
运行代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
// 数组是否存在两个数，它们的和为 target？
boolean hasTargetSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return true;
}
}
}
return false;
}
算法包含两个 for 循环嵌套，所以时间复杂度是 O(n²)，其中 n 代表 nums 数组的长度。
我们的算法只使用了 i, j 两个变量，这是常数级别的空间消耗，所以空间复杂度是 O(1)。
你也许会说，内层的 for 循环并没有遍历整个数组，且有可能提前 return，算法实际执行的次数应该是小于 n²的，时间复杂度还是 O(n²)吗？
是的，还是 O(n²)。前面说了 Big O 表示法是估计值，不需要精确计算。具体到不同的输入，算法的实际执行次数确实会小于 n²，但我们不需要关心。
简单说就是：看到嵌套 for 循环，时间复杂度就是 O(n²)。
示例四，时间复杂度 O(n)，空间复杂度 O(n)：
Java
运行代码
复制代码
1
2
3
void exampleFn(int n) {
int[] nums = new int[n];
}
这个函数中创建了一个大小为 n 的数组，所以空间复杂度是 O(n)。
申请数组空间及初始化数组也需要时间，所以时间复杂度也是 O(n)。
时间复杂度并不仅仅体现在你看得到的 for 循环，每一行代码都可能有隐藏的时间复杂度。所以说要了解常见数据结构的实现原理，这是准确分析时间复杂度的基础。
示例五，时间复杂度 O(n)，空间复杂度 O(n)：
Java
运行代码
复制代码
1
2
3
4
5
6
7
8
// 输入一个整数数组，返回一个新的数组，新数组的每个元素是原数组对应元素的平方
int[] squareArray(int[] nums) {
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
res[i] = nums[i] * nums[i];
}
return res;
}
算法初始化 res 数组需要 O(n)的时间复杂度，包含一个 for 循环，时间复杂度也是 O(n)，总的时间复杂度是还是 O(n)其中 n 代表 nums 数组的长度。
我们声明了一个新的数组 res，这个数组的长度和 nums 数组一样，所以空间复杂度是 O(n)。
