一般来说，看循环中有多少个变量
(1)、O(1)
常数
O(1)就是最低的时空复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。
哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）
Temp=i; i=j; j=temp;
(2)、O(logn)
一个循环，有条件会退出
当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。
二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。
class Demo {
public static void main(String[] args){
i = 1;
while (i <= n) {
i = i * 2;
}
}
}
此段代码的时间复杂度就取决于while里面那句话的执行次数，也就是i和n的关系。
i每次在乘以2之后都会更加逼近n，也就是说，在有x次后，i将会大于n从而跳出循环，
i = 2^x <= n
2푥 = 푛 ,也就是푥=푙표푔2푛，
所以：
时间复杂度T(n) = O(f(n)) = O(logn)
(3)、O(n)
一个循环
数据量增大几倍，耗时也增大几倍。比如常见的遍历算法。
for(int i = 0; i < n; i++) { // 1次 n+1次 n次
if(seq[i] == value) { // n次
return i; // 1次
}
}
时间复杂度T(n) = O(f(n)) = O(1 + (n + 1) + n + n + 1) = O(3n + 3) = O(n)
(4)、O(nlogn)
两个以上循环，有条件会退出
n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。
归并排序就是O(nlogn)的时间复杂度。
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j=j*2)
{
printf("aaa");
}
}
外层循环n次，内层循环logn次(logn表示以2为底n的对数)，外层的n次就不用算了,一看就知道。
内层为什么会循环logn次？
第1次循环后：j=2
第2次循环后：j=4
第3次循环后：j=8
第4次循环后：j=16
…
第x次循环后:j=2^x
因为j<=n，所以2^x<=n，得x<=logn，最多循环logn次，所以总共循环nlogn次,
即时间复杂度为O(nlogn)
(5)、O(n^2)
两个循环
数据量增大n倍时，耗时增大n的平方倍。
比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。
long FindInversions(int[] array){
long inversions = 0;
for (int i = 0; i < array.Length; i++){
for (int j = i + 1; j < array.Length; j++){
if (array[i] > array[j])
inversions++;
}
}
return inversions;
}
执行数量约为 n*(n-1)/2，复杂度为 O(n^2)。
(6)、O(n^3)
三个循环
decimal Sum3 (int n) {
decimal sum = 0;
for (int a = 0; a < n; a++)
for (int b = 0; b < n; b++)
for (int c = 0; c < n; c++)
sum += a * b * c;
return sum;
}
给定规模 n，则基本步骤的执行数量约为 nnn ，所以算法复杂度为 O(n3)。
(7)、O(2^n)
循环中带有方法
decimal Calculation(int n) {
decimal result = 0;
for (int i = 0; i < (1 << n); i++)
result += i;
return result;
}
给定规模 n，则基本步骤的执行数量为 2n，所以算法复杂度为 O(2^n)。
<<是左移
循环中带有方法，重新执行原方法
int Fibonacci(int n) {
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
给定规模 n，计算 Fib(n) 所需的时间为计算 Fib(n-1) 的时间和计算 Fib(n-2) 的时间的和。
T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)
fib(5)
/
fib(4) fib(3)
/ /
fib(3) fib(2) fib(2) fib(1)
/ / /
通过使用递归树的结构描述可知算法复杂度为 O(2^n)。
(8)、O(n! )
循环中带有方法
写出1~n的所有全排列
自然数n的阶乘
亦即n!=1×2×3×…×n。阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。
def permutation(_in):
if len(_in) == 0:
return []
if len(_in) == 1:
return [_in]
out = []
for i in range(len(_in)):
m = _in[i]
rem = _in[:i] + _in[i + 1:]
for p in permutation(rem):
out.append([m] + p)
return out
for p in permutation(list('abc')):
print(p)
(9)、O(n^n)
循环中带有方法
// Returns minimum number of
// jumps to reach arr[h] from arr[l]
static int minJumps(int arr[], int l, int h)
{
// base case: when source
// and destination are same
if (h == l)
return 0;
// When nothing is reachable
// from the given source
if (arr[l] == 0)
return Integer.MAX_VALUE;
// Traverse through all the points
// reachable from arr[l]. Recursively
// get the minimum number of jumps
// needed to reach arr[h] from these
// reachable points.
int min = Integer.MAX_VALUE;
for (int i = l + 1; i <= h
&& i <= l + arr[l];
i++) {
int jumps = minJumps(arr, i, h);
if (jumps != Integer.MAX_VALUE && jumps + 1 < min)
min = jumps + 1;
}
return min;
}
我可以将递归关系看作T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) + … + T(0)，因为循环是从l到h的（暂时忽略if条件）。
所以对于区间[l,h]，在最坏的情况下，minJumps(l+1, h), minJumps(l+2, h) … minJumps(h, h)会调用该区间中的每个值，可以注意到上面的递归关系在这里成立。
现在，解决这个关系，我们可以把它写成T(n) = T(n-1) + T(n-1)和T(n-1) = T(n-2) + T(n-3) + T(n-4) + … + T(0)。
因此T(n) = 2 * T(n-1)可以归结为O(2^n)。
该算法的时间复杂度应为O(2^n)。
^n一般来说，是方式内调方式
几种常见时间复杂度实例
1.常量阶 O(1)
2.对数阶 O(logn)
3.线性阶 O(n)
4.线性对数阶 O(nlogn)
5.平方阶 O(n2)、立方阶 O(n3)……k 次方阶 O(nk)
6.指数阶 O(2n)
7.阶乘阶 O(n!)
