概述

时间复杂度

时间复杂度和空间复杂度都是在编写代码时对代码运行效率的一个预估，一般以n代之问题规模，以一个n为自变量的函数对问题的时间或空间上的复杂度进行描述。
一般的有以下几个常用的时间复杂度的函数

• O(1) - 代码执行常数次，与n无关
• O(n) - 代码执行kn次，问题规模为n的一次方，如常见的遍历操作
• O(n^2) - 代码执行kn^2次，问题规模为n的二次方，常见的如二维遍历操作。
• O(n^m) - 同理
• O(logn) - 代码执行klog2(n)次，指问题规模翻倍时，操作次数加一，常见的如二分查找。
• O(nlogn) - O(n)与O(logn)的嵌套，常见的如归并排序。
• O(2^n) - 指数级别的增长，指问题规模加一时，操作次数翻倍

简单根据操作次数进行一个排序可以得到：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^m) < O(2^n)

• 只能大概进行衡量，具体还需要根据n的规模进行比较。

函数图形

空间复杂度

相对的，空间复杂度是对程序运行过程中占用空间的一种预估，对空间复杂度的预估往往需要着眼与程序运行过程中临时分配的内存空间，同样将这一空间的大小与问题规模n建立联系。简单的可以归纳为

• 如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示;
• 如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n2) 表示；
• 如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n3) 表示；
• …

小结

在编写算法时，空间与时间往往是鱼和熊掌难以兼得，空间换时间或者时间换空间都是常用有效的策略。