算法复杂度用于分析算法运行所需计算机资源的量，需要的时间资源为时间复杂度，需要的空间资源为空间复杂度。在我们判断一个算法的优劣时，可以抛开软件和硬件因素，只考虑问题的规模。编写程序前预先估计算法优劣，可以改进并选择更高效的算法。
一、时间复杂度
编程实现算法后，算法就是由一组语句构成，算法的执行效率就由各语句执行的次数所决定。一个算法花费的时间与算法中语句的执行次数成正比，哪个算法语句执行次数多，它花费的时间就多，把时间复杂度记为 T(n)，一般情况下，算法的基本操作重复执行的次数是关于模块 n 的一个函数 f(n)，因此，我们可以把算法的时间复杂度记做：T(n)=O(f(n))。
随着模块 n 的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。我们研究复杂度的目的是要比较两个算法的效率的高低，并不需要仔细地分析这个算法比那个算法多几次运算那么清，所以我们采用渐近复杂度分析来比较算法的效率。我们在分析算法的时间复杂度时，一般都会规定各种输入情况得出最好情况下 Tmax(n) 、最坏情况下 Tmin(n) 和平均情况下 Tavg(n) 。
1. 求绝对值
我们需要求一个整数的绝对值，在算法设计上，只需要输入的值为负数时，返回它的相反数，其他情况返回本身，代码如下：
public static int abs(int a) { return a < 0 ? -a : a; }
该代码中只有一条运算指令语句，时间复杂度为 O(1)。
2. 数组求和
已知一个整型数组，需要对数组内所有元素求和，如果只是通过遍历所有元素而不使用其他方法进行求和，可以使用如下代码实现：
public static int sum(int[] a) { int s = 0; for (int i : a) { s += i; } return s; }
由代码可知，如果输入数组的大小为 n ，执行语句中初始化赋值需要时间 O(1)，循环语句中的赋值操作需要时间为 O(1)*n，所以语句执行的时间为：O(1)+O(1)*n=O(n+1)=O(n)。
3. 二分查找
已知一个有序数组，需要在数组中找到某个元素的位置，我们可以通过二分法来实现，代码如下：
public static int binarySearch(int[] a, int b) { int i, r = 0, l = a.length; while (r <= l) { i = (r + l) / 2; if (a[i] < b) { r = i + 1; } else if (a[i] > b) { l = i - 1; } else { return i; } } return -1; }
我们要计算此代码的时间复杂度，关键就是算循环的次数，可以归纳一下，在最糟糕的情况下：
- 在4个元素中查找需要2步；
- 在8个元素中查找需要3步；
- 在16个元素中查找需要4步；
- 在 n 个元素中查找需要 log2n 步。
也就是说在 n 个元素中，需要当 n/(2^k)=1 时，才能找到目标元素，由此也可得到 k=log2n ，所以二分查找的时间复杂度为 O(log n)。
4. 冒泡排序
已知一个整型数组，需要使用冒泡算法来进行排序，代码实现如下：
public static int[] bubbleSort(int[] a) { int temp; for (int i = 0; i < a.length - 1; i++) { for (int j = 0; j < a.length - 1 - i; j++) { if (a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } return a; }
在上面代码中，两层循环中比较的次数为 (n-1)+(n-2)+(n-3)+...+1 ，根据等差数列求和公式得出结果为 n(n-1)/2 ，忽略低次项，所以该算法的时间复杂度为 O(n^2)。
二、空间复杂度
衡量算法性能的另一个重要方面，就是算法需使用的存储空间量，即算法空间复杂度。我们希望对于同样的输入规模，在时间复杂度相同的前提下，算法所占的空间越少越好。每次基本操作只会涉及到常数规模的空间，所以我们在分析和讨论算法时，只关注时间复杂度。当然，空间复杂度在对空间效率非常在乎的应用场景时，或者是问题的输入规模极为庞大时，也有其存在的意义。
