在满足准确性和健壮性的基础上，还有一个重要的筛选条件，即通过算法所编写出的程序的运行效率。程序的运行效率具体可以从 2 个方面衡量，分别为：
程序的运行时间。程序运行所需内存空间的大小。

时间复杂度

也就是说，表示一个算法所编程序运行时间的多少，用的并不是准确值（事实上也无法得出），而是根据合理方法得到的预估值。

实际场景中，我们更喜欢用一个估值来表示算法所编程序的运行时间。所谓估值，即估计的、并不准确的值。注意，虽然估值无法准确的表示算法所编程序的运行时间，但它的得来并非凭空揣测，需要经过缜密的计算后才能得出。

以一段简单的 C 语言程序为例，预估出此段程序的运行时间：

for(int i = 0 ; i < n ; i++)     //<- 从 0 到 n，执行 n+1 次
{
    a++;                         //<- 从 0 到 n-1，执行 n 次
}
1
2
3
4

时间复杂度为2n+1；去掉常数和系数 n非常大时估算为n；

再举一个例子：

for(int i = 0 ; i < n ; i++)           // n+1
{ 
    for(int j = 0 ; j < m ; j++)       // n*(m+1)
    {
        num++;                         // n*m
    }
}
1
2
3
4
5
6
7

估算为n*n，可以用最内层num执行的次数进行估算

如下列举了常用的几种时间复杂度，以及它们之间的大小关系：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)

空间复杂度

是对算法运行过程中临时占用空间大小的度量，一个算法所需的存储空间用 f (n) 表 示，可得出 S(n) = O(f(n)) ，其中 n 为问题的规模， S(n) 表示空间复杂度。通常用 S(n) 来定义。

O(1) 复杂度

算法执行所需要的临时空间不随着某个变量 n 的大小而变化，即此算法空间复杂度为一个常量， 可表示为 O(1)

int n;
scanf("%d", &n);
int a[10];
1
2
3

以上代码，分配的空间不会随着处理数据量的变化而变化，因此得到空间复杂度为 O(1)

O(n) 复杂度

int n;
scanf("%d", &n);
int a[n];
1
2
3

上面这段代码的第一行，申请了长度为 n 的数组空间，下面的 for 循环中没有分配新的空间，可 以得出这段代码的时间复杂度为 O(n)。

对数阶的空间复杂度非常少见，而且空间复杂度的分析相对与时间复杂度分析简单很多，这部分不再阐述。

时间空间相互转换

对于一个算法来说，它的时间复杂度和空间复杂度往往是相互影响的。

那我们熟悉的 Chrome 来说，流畅性方面比其他厂商好了多人，但是占用的内存空间略大。

当追求一个较好的时间复杂度时，可能需要消耗更多的储存空间。 反之，如果追求较好的空间复杂 度，算法执行的时间可能就会变长。

总结
常见的复杂度不多，从低到高排列就这么几个: O(1) 、 O(log(n)) 、 O(n) 、 O(n2)