时间复杂度

为什么要有时间复杂度？

第一、在我们的测试环境里面，不同的硬件跑出来的结果是不一样的，比如，i7与i3的机器跑同样的代码花的时间就不一样。

第二、用不同的数据去测试，那么花的时间也是不一样的。

通用公式

所以我们需要一套公式去计算复杂度，通用公式：T = O(N)，T表示代码执行的时间，N表示每行代码执行的次数总和，O表示所有代码的执行时间T与每行代码的执行次数总和成正比。（假设每行代码执行的时间是一样的）

O表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

开始运用方法：

方法一. 只关注循环执行次数最多的一段代码

int cal(int n) { 
     int sum = 0; 
     int i = 1; 
     for (; i <= n; ++i) { 
        sum = sum + i;
     }
     return sum;
 }

其中2、3行是常量级别的代码与n的大小无关，所有不用管，执行次数最多的事第4、5行代码，所以我们只管这个两行，时间复杂度是O(n).

方法二、乘法法则，嵌套代码的复杂度等于内外嵌套复杂度的乘积

int cal(int n) {
	int ret = 0;
	int i = 1;
	for (; i < n; ++i) { //第一段 这个函数的复杂度是O(n)
		ret = ret + f(i);
	}
}
int f(int n) {
	int sum = 0;
	int i = 1;
	for (; i < n; ++i) {//第段段 这函数的复杂度是O(n),合起来就是O(n^2)
		sum = sum + i;
	}
	return sum;
}

这里单看第一段函数的复杂度是O(n)，单看第二段函数的复杂度也是O(n)，有因为嵌套了，合在一起就是O(n^2)了。

方法三、计算复杂度是总复杂度最多的那段

int cal(int n) {
	int sum_1 = 0;
	int p = 1;
	for (; p < 100; ++p) {//第一段为O(1)
		sum_1 = sum_1 + p;
	}
	int sum_2 = 0;
	int q = 1;
	for (; q < n; ++q) {//第二段为O(n)
		sum_2 = sum_2 + q;
	}
	int sum_3 = 0;
	int i = 1;
	int j = 1;
	for (; i <= n; ++i) {//第三段为O(n^2)
		j = 1;
		for (; j <= n; ++j) { //这里又套了一层循环
			sum_3 = sum_3 +  i * j;
		}
	}
	return sum_1 + sum_2 + sum_3;
}

第一段的执行的次数是常量，所以是O(1),第二段执行了n次所以是O(n)，第三段执行了O(n2)，所以这段代码最终的时间复杂度为O(n^2)

再看看常见的多项式时间复杂度

第一种：O(1)

int i = 8;
int j = 6;
int sum = i + j;

这种情况，主要没有递归、循环，即使有上千万行的代码，时间复杂度也是O(1)

第二种： O(logn)、O(nlogn)

 i=1;
 while (i <= n)  {
   i = i * 2;
 }

由上可知道，它的代码执行轨迹就是：2^1 * 2^2 * 2^3 * 2^4 …… 2^x = n 为止，那么求解这个X，就是以2为底的log函数：x=log2n，所以这段代码的时间复杂度是O(log2n)，如果在外面再套一层循环m，那么时间复杂度就是O(m*log2n)

第三种：O(m+n)、O(m*n)

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {//第一段复杂度为O(n)
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {//第二段复杂度为O(m)
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

第一段和第二段的复杂分别是O(n)和O(m),属于同一级别，都是n级别(大于1，小于N的平方)，所以cal()方法的复杂度是O(m+n)，如果第一段和第二段有嵌套的话，那么可以相乘：O(m*n)

空间复杂度分析

空间复杂度就很简单了，就是一句“占用有多少个变量”就可以解释完毕！

void print(int n) {
  int i = 0;
  int[] a = new int[n]; // 只有这里占用了n个空间所以空间复杂度是O(n)
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

}

从上面可以看出，只有第3行 new的时候占用了n个空间，其它行占用的空间是O(1)，所以答案是O(n)

我们平时能用的空间复杂度一般是是O(1),O(n),O(n^2)，其他的O(logn)、O(nlogn)都是用不到的

继续拓展

=========分割线==========

复杂的时间复杂度该怎么算？有下面的问题：

// 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;
       break;
    }
  }
  return pos;
}

这个空间复杂度用上面的方法显示不不行的。

        如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 O(1)。但如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。所以，不同的情况下，这段代码的时间复杂度是不一样的。

这个需要用到概率论来解决，想继续钻研的朋友可以扫码下面的二维码，听听专业老师的讲解。

时间复杂度的概念。

定义：存在常数 c 和函数 f(N)，使得当 N >= c 时 T(N) <= f(N)，表示为 T(n) = O(f(n)) 。
 

很多时候一眼就能看出程序的时间复杂度，但是遇到复杂的就需要将其过程推导出来，为此总结以下两种形式

一、循环主体中的变量参与循环条件的判断
找出主体语句中与T(n)成 正比的循环变量，带入进行计算，例如：
int i = 1;
while(i <= n)
    i = i*2;
其中i*2的次数与T(n)成正比，则2的T(n)次方<= n,则T(n)<=log2n。

二、循环主体中的变量与循环条件无关
可采用数学归纳法或者直接累计循环次数，多层循环时从内到外分析，只关注主体语句执行次数。这种情况分为递归程序和非递归程序
递归程序一般使用公式进行递推，例如：
int fact (int n){
    if(n<=1) return 1;
    return n*fact(n-1);
}
T(n)=1+T(n-1)=1+1+T(n-2)= ...=n-1+T(1)
则T(N)=O(n).
非递归程序比较简单，可以直接累计次数

原文链接：https://blog.csdn.net/Hearbeat/article/details/76222930

计算时间复杂度--（简单版）

步骤：
1、找到执行次数最多的语句

2、语句执行语句的数量级

3、用O表示结果

计算时间复杂度的3个出发点，掌握这三个出发点，那么一向搞不懂的时间复杂度就可以迎刃而解啦。

然后：

1、用常数1取代运行时间中的所有加法常数

2、在修改后的运行次数函数中，只保留最高阶项

3、如果最高阶项存在且不是1，那么我们就去除于这个项相乘的常数。比如3n^2我们取n^2

最后就可以得到你们想要的结果了。

举几个例子：

我们来看一下这个例子，用的是java，内容就是打印8条语句，问这个程序的时间复杂度是多少？

public class TS {
    public static void main(String[] args) {
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
    }
}
 

O（8）？ 当然不是！！！按照时间复杂度的概念“T（n）是关于问题规模为n的函数”，这里跟问题规模有关系吗？没有关系，用我们的第一个方法，时间复杂度为O（1）。

第二个例子：（线性阶）

 
public class TS {
    public static void main(String[] args) {
        int sum = 0;
        for(int i=1;i<=100;i++) {
            sum = sum + i;
        }
    }
}
时间复杂度为O（n）。

第三个例子：（平方阶）

 
public class TS {
    public static void main(String[] args) {
        int sum = 0;
        for(int i=1;i<=100;i++) {
            for(int j=1;j<=100;j++)
                sum = sum + i;
        }
    }
}
 外层i的循环执行一次，内层j的循环就要执行100次，所以外层执行100次，那么总的就需要执行100*100次，那么n次呢？就是n的平方次了。所以时间复杂度为：O（n^2）。

平方阶的另外一个例子：

public class TS {
    public static void main(String[] args) {
        int sum = 0;
        for(int i=1;i<=100;i++) {
            for(int j=i;j<=100;j++)
                sum = sum + i;
        }
    }
}
当i=1的时候执行n次，当n=2的时候执行（n-1）次，......

一直这样子下去就可以构造出一个等差数列：n+（n-1）+（n-2）+......+2+1

根据等差数列的求和公式：或者

求和易得：n+n*(n-1)/2整理一下就是n*(n+1)/2然后我们将其展开可以得到n^2/2+n/2。

根据我们的步骤走，保留最高次项，去掉相乘的常数就可以得到时间复杂度为：O（n^2）

第四个例子：（对数阶）

public class TS {
    public static void main(String[] args) {
        int i=1;
        int n= 100;
        while(i<n) {
            i = i*2;
        }    
}
2^x = n,所以时间复杂度为O(log2n)。

补充常用的时间复杂度所耗费的时间从小到大依次是：
O(1 )< O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

最坏情况与平均情况：
平均运行时间是期望的运行时间。最坏的运行时间是一种保证。我们提到的运行时间都是最坏的运行时间。可以通过空间来换取时间。

原文链接：https://blog.csdn.net/szlg510027010/article/details/82426240

https://www.jianshu.com/p/f4cca5ce055a

出自：https://blog.csdn.net/virus2014/article/details/52274849

定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数T(n)称为这一算法的“时间复杂性”。

当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是 最佳算法。

“大O记法”：在这种描述中使用的基本参数是 
n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;                    

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1. 
交换i和j的内容

sum=0；                 （一次）
for(i=1;i<=n;i++)       （n次 ）
for(j=1;j<=n;j++)（n^2次 ）
sum++；       （n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2)

2.2.

for (i=1;i<n;i++) {
    y=y+1;         ①   
    for
    (j=0;j<=(2*n);j++)    
    x++;        ②      
}   

解： 
语句1的频度是n-1 
语句2的频度是(n-1)*(2n+1)=2n^2-n-1 
f(n)=2n^2-n-1+(n-1)=2n^2-2 
该程序的时间复杂度T(n)=O(n^2).

O(n)

2.3.

a=0;
b=1;                      ①
for(i=1;i<=n;i++){ ②  
    s=a+b;　　　　③
    b=a;　　　　　④  
    a=s;　　　　　⑤
}

解：语句1的频度：2, 
语句2的频度：n, 
语句3的频度： n-1, 
语句4的频度：n-1, 
语句5的频度：n-1, 
T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n) 
2.4.

i=1;       ①
while (i<=n)
    i=i*2; ②

解： 语句1的频度是1, 
设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n 
取最大值f(n)=log2n, T(n)=O(log2n )

O(n^3)

2.5.

    for(i=0;i<n;i++)
    {  
       for(j=0;j<i;j++)  
       {
          for(k=0;k<j;k++)
             x=x+2;  
       }
    }

解：当i=m, 
j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,…,m-1 , 所以这里最内循环共进行了0+1+…+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+…+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).

我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次都仔细 地选择基准值，我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。

下面是一些常用的记法： 
访问数组中的元素是常数时间操作，或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3)，因为算出每个元素都需要将n对元素相乘并加到一起，所有元素的个数是n^2。 
指数时间算法通常来源于需要求出所有可能结果。例如，n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了，除非n的值非常小，因为，在 这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 (如著名的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果的算法替代之。

计算方法

1.一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。

一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

2.一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））。随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。

在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））。

3.常见的时间复杂度

按数量级递增排列，常见的时间复杂度有：常数阶O(1), 对数阶O(log2n), 线性阶O(n), 线性对数阶O(nlog2n), 平方阶O(n^2)， 立方阶O(n^3),…， k次方阶O(n^k), 指数阶O(2^n) 。

其中，

1.O(n)，O(n^2)， 立方阶O(n^3),…， k次方阶O(n^k) 为多项式阶时间复杂度，分别称为一阶时间复杂度，二阶时间复杂度……

2.O(2^n)，指数阶时间复杂度，该种不实用

3.对数阶O(log2n), 线性对数阶O(nlog2n)，除了常数阶以外，该种效率最高

例：算法：

  for（i=1;i<=n;++i）
  {
     for(j=1;j<=n;++j)
     {
         c[ i ][ j ]=0; //该步骤属于基本操作 执行次数：n^2

          for(k=1;k<=n;++k)
               c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数：n^3
     }
  }

则有 T（n）= n^2+n^3，根据上面括号里的同数量级，我们可以确定 n^3为T（n）的同数量级 
则有f（n）= n^3，然后根据T（n）/f（n）求极限可得到常数c 
则该算法的 时间复杂度：T（n）=O（n^3)