Basic Time Complexity
考虑到这是第一章，我不会对时空复杂度做面面俱到的讲解，详细的 算法时空复杂度分析实用指南 安排在你学完几种常见算法的核心框架之后，那时候你的知识储备可以轻松理解时空复杂度分析的各种场景。
因为本章后面的内容会带你实现常见的排序算法和数据结构，我会分析它们的时间复杂度，所以这里还是要提前介绍一下时间/空间复杂度的概念，以及分析时间/空间复杂度的简化方法，避免初学者疑惑。
对于初学者，你只需要记住以下几点：
1、时空复杂度用大 O 表示法表示（类似 O(1), O(n^2), O(logn) 等）。它们都是估计值，不需要精确计算。
2、时间复杂度用来衡量一个算法的执行效率，空间复杂度用来衡量算法的内存消耗，它们都是越小越好。
比方说时间复杂度 O(n) 的算法比 O(n^2) 的算法执行效率高，空间复杂度 O(1) 的算法比 O(n) 的算法内存消耗小。
当然，一般我们要说明这个 n 代表什么，比如 n 代表输入的数组的长度。
3、如何估算？现在你可以简单理解：时间复杂度就看 for 循环的嵌套层数；空间复杂度就看算法声明了多少空间来存储数据。
注意
我这里说按照 for 循环的嵌套层数来估算时间复杂度仅是简化的方法，其实是不准确的。正确的方法会在 算法时空复杂度分析实用指南 介绍，但是对于初学者学习本章内容来说，这种估算方法足够用了。
举几个例子来说比较直观。
示例一，时间复杂度 O(n)，空间复杂度 O(1)：
// input an integer array, return the sum of all elements
int getSum(int[] nums) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
return sum;
}算法包含一个 for 循环遍历 nums 数组，所以时间复杂度是 O(n)，其中 n 代表 nums 数组的长度。
我们的算法只使用了一个 sum 变量，这个 nums 是题目给的输入，不算在我们算法的空间复杂度里面，所以空间复杂度是 O(1)。
示例二，时间复杂度 O(n^2)，空间复杂度 O(1)：
// Does the array contain two numbers whose sum is 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^2)，其中 n 代表 nums 数组的长度。
我们的算法只使用了 i, j 两个变量，这是常数级别的空间消耗，所以空间复杂度是 O(1)。
你也许会说，内层的 for 循环并没有遍历整个数组，且有可能提前 return，算法实际执行的次数应该是小于 n^2 的，时间复杂度还是 O(n^2) 吗？
是的，还是 O(n^2)。前面说了大 O 表示法是估计值，不需要精确计算。具体到不同的输入，算法的实际执行次数确实会小于 n^2，但我们不需要关心，嵌套 for 循环，时间复杂度就是 O(n^2)。
示例三，时间复杂度 O(n)，空间复杂度 O(n)：
// input an integer array, return a new array where each element is the square of the corresponding element in the original array
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;
}算法只包含一个 for 循环，所以时间复杂度是 O(n)，其中 n 代表 nums 数组的长度。
我们声明了一个新的数组 res，这个数组的长度和 nums 数组一样，所以空间复杂度是 O(n)。
好了，初学者明白上面这些基本的时间、空间复杂度分析暂时就够用了，继续往下学习吧。