非多项式量级。非多项式量级只有两个： O(2^n) 和 O(n!)。当数据规模n越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。
1、Q(1)O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有3行，它的时间复杂度也是O(1），而不是O(3)。
int i = 8; int j = 6; int sum = i + j;只要代码的执行时间不随n的增大而增长，这样代码的时间复杂度我们都记作O(1)。或者说， 一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
2、Q(logn)、Q(nlogn)对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。通过一个例子来说明一下。
i=1; while (i <= n) { i = i * 2; }根据我们前面讲的复杂度分析方法，第三行代码是循环执行次数最多的。所以，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。
从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。
这是一个等比数列。把它一个一个列出来，就应该是这个样子的： 2^0, 21,22, 2^x... = n
所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2^x = n 求解 x 。x=log2n，所以，这段代码的时间复杂度就是O(log2n)。
在看一个例子：
根据上面的思路，很简单就能看出来，这段代码的时间复杂度为 O(log3n)。
实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。
因为对数之间是可以互相转换的， log3n 就等于log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C = log32 是一个常量。
基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。
因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。
基于上面的关系，那 O(nlogn) 就很容易理解了。还记得我们刚讲的乘法法则吗？如果一段代码的时间复杂度是 O(logn)，我们循环执行n遍，时间复杂度就是 O(nlogn)了。
O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。
3、Q(m+n)、Q(m * n)代码的复杂度由两个数据的规模来决定。
int cal(int m, int n) { int sum_1 = 0; int i = 1; for (; i < m; ++i) { sum_1 = sum_1 + i; } int sum_2 = 0; int j = 1; for (; j < n; ++j) { sum_2 = sum_2 + j; } return sum_1 + sum_2; }从代码中可以看出， m 和n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大。
所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一 个。所以，上面代码的时间复杂度就是 O(m+n)。
针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为： T1(m) + T2(n) = O(f(m) + g(n))。
但是乘法法则继续有效： T1(m) * T2(n) = O(f(m) * f(n))
二、空间复杂度空间复杂度全称就是渐进空间复杂度（asymptotic space complexity）， 表示算法的存储空间与数据规模之间的增长关系。
举个例子：
跟时间复杂度分析一样，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。
第3行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。
我们常见的空间复杂度就是 O(1)、 O(n)、 O(n² )，像 O(logn)、 O(nlogn) 这样的对数阶复杂度平时都用不到。
空间复杂度分析比时间复杂度分析要简单很多。
三、浅析最好、最坏、平均、均摊时间复杂度 3.1、最好、最坏情况时间复杂度 // n表示数组array的长度 int find(int[] array, int n, int x) { int i = 0; int pos = -1; for (; i < n; ++i) { if (array[i] == x) pos = i; } return pos; }你应该可以看出来，这段代码要实现的功能是，在一个无序的数组（array）中，查找变量 x 出现的位置。如果没有找到，就返回-1。
按照上面讲的分析方法，这段代码的复杂度是 O(n)，其中， n 代表数组的长度。