纯纯的复习, 主打的就是一手温故知新.

定义

时间复杂度是对时间增长速度的一个估计

  • 可以简单的用极限理解，若所有指令总执行次数T，时间复杂度为O(f(n))的算法表示 = K（K为常数）。

例如T1=n2+n，T2=2n2-n，通过极限的思想得到这两个算法的f(n)=n即时间复杂度都是O(n)

  • 因为log2n=log23*log3n，而log23是常数，所以O(log2n)=O(log3n),考虑复杂度时,所有的log都尽量写成log2n或者logn的形式。

举3个栗子搞定时间复杂度

Demo1(每一层的变量都是自增1)

1
2
3
4
5
for (i=0;i<n;i++)
      for (j=0;j<n;j++)
          for (k=0;k<n;k++)
             if (A[i][j]>A[i][k]+A[k][j])
                 A[i][j]>A[i][k]+A[k][j];

上面代码的每一层都是变量自增，且变量都是从0~n-1共n次，所以总次数是n3，时间复杂度是O(n3)

Demo2(每一层的变量都是自增1，但第二三层变量取值范围和第一层变量有关)

1
2
3
4
5
for (i=0;i<n;i++)
      for (j=0;j<i;j++)
          for (k=0;k<j;k++)
             if (A[i][j]>A[i][k]+A[k][j])
                 A[i][j]>A[i][k]+A[k][j];

时间复杂度和第①种一样，但不用考虑具体次数，时间复杂度是O(n3)

Demo3(对于两层循环，变量不是自增1)

1
2
3
for (i=1;i<n;i*=2) //22考研真题
      for (j=0;j<i;j++)
          sum++;

需要讨论第一层变量i取不同值时，j的取值有x种，然后对x求和。

比如本题，i=1, 2, 4, 8…2k(2k<n≤2k+1)时，第二层j有i个取值，所以总次数是对i求和，即T=1+2+4+2k=2k+1-1，n<T<2n，时间复杂度就是O(n)。

常见的时间复杂度排序

O(1)< O(log2(n))< O(n)< O(nlog2(n)< O(n^2)< O(n^3)< O(2^n)< O(n!)< O(n^n)

递归次数对时间复杂度的影响

递归总次数和时间复杂度有关，而最大递归层数和空间复杂度有关。

对于树中序遍历的递归写法，每个节点都会调用一次所以总共调用次数是O(n)级别的，时间复杂度是O(n)，而递归使用的层数最多是树高h，空间复杂度是O(h)。

1
2
3
4
5
6
void inorder(BTNode *p){
    if (p==NULL) return;
  	inorder(p->lchild);
  	visit(p);                           //对p节点的访问等
 	  inorder(p->rchild);
}

空间复杂度

和时间复杂度类似，一个算法的空间复杂度，也常用大 O 记法表示。

简单的说就是程序运行所需要的空间。要知道每一个算法所编写的程序，运行过程中都需要占用大小不等的存储空间，例如：

  • 程序代码本身所占用的存储空间；
  • 程序中如果需要输入输出数据，也会占用一定的存储空间；
  • 程序在运行过程中，可能还需要临时申请更多的存储空间。

首先，程序自身所占用的存储空间取决于其包含的代码量，如果要压缩这部分存储空间，就要求我们在实现功能的同时，尽可能编写足够短的代码。

程序运行过程中输入输出的数据，往往由要解决的问题而定，即便所用算法不同，程序输入输出所占用的存储空间也是相近的。

事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间。不同的算法所编写出的程序，其运行时申请的临时存储空间通常会有较大不同。

单个定义的变量都不需要考虑，但定义的数组中元素个数以及链表中节点个数都要计入空间复杂度中。