实际上，我们可以用三种不同的方式描述算法的运行时。
让我们从快速排序的角度来看一下。快速排序选择一个随机元素作为“基准（pivot）”，然后交换数组中的值，以使小于基准的元素出现在大于基准的元素之前。这给出了“部分排序”，然后使用类似的过程递归地对左右两边排序。
-
最佳情况：如果所有元素都相等，那么快速排序平均将只遍历数组一次。这是 O(N)。（这实际上在某种程度上取决于快速排序的实现。但是，有些实现将在有序数组上非常快地运行。）
-
最坏的情况：如果我们真的很不幸，选取的基准屡次是数组中的最大元素，该怎么办？ （实际上，这很容易发生。如果选择子数组中的第一个元素为基准，并且以相反的顺序对数组进行排序，就会遇到这种情况。）在这种情况下，我们的递归不会将数组分成两半，而是在每一半上递归。它只是将子数组缩小了一个元素。这将退化为O(N^2) 运行时。
-
预期情况：尽管如此，通常这些完美或糟糕的情况不会发生。当然，有时基准会非常低或非常高，但不会一次又一次地发生。我们可以期望运行时间为 O(N log N)。
空间复杂度是一个与时间复杂度平行的概念。如果我们需要创建一个大小为 n 的数组，这将需要 O(n) 空间。如果我们需要一个大小为 n x n 的二维数组，则将需要 O(n^2) 空间。
递归调用中的堆栈空间也很重要。例如，这样的代码将占用 O(n) 时间和 O(n) 空间。
1 int sum(int n) { /* Ex 1. */
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n-1);
6 }每个调用都会向堆栈添加一层。
1 sum(4)
2 -> sum(3)
3 -> sum(2)
4 -> sum(1)
5 -> sum(0)
每个调用都被添加到调用堆栈，并占用实际内存。
Add the Runtimes： O(A + B)
1 for (int a ： arrA) {
2 print(a);
3 }
4
5 for (int b ： arrB) {
6 print(b);
7 }Multiply the Runtimes：O(A*B)
1 for (int a ： arrA) {
2 for (int b ： arrB) {
3 print(a + "," + b);
4 }
5 }当你看到一个问题时，如果问题空间（problem space）中的元素数量每次减半，那么运行时可能就是 O(log N)。
这段代码的运行时间是多少？
1 int f(int n) {
2 if (n <= 1) {
3 return 1;
4 }
5 return f(n - 1) + f(n - 1);
6 }这是一个很平衡的二叉树递归结构 所以是O(2^N)