算法时间复杂度的计算方法简介

何为算法的时间复杂度？简单点说就是程序中基本操作的执行次数和问题规模的大小，通常用O(f(n))表示。

在计算算法时间复杂度的时候，记住两个要点：

1.只考虑高阶项。

2.不需要保留系数。记住，不需要系数！！！

下面，我们用例题来让大家感受一下算法时间复杂度的计算方法！

例1：

{++x;s=0;}

++x和s=0都是它的基本操作，两条语句都执行一次，f(n)=2=2*1;但是在计算时间复杂度中第二个要点表明不需要保留系数，去掉系数2，那么，其时间复杂度就是O(1)。这里的O(1)表示常数次。

例2：

for(int i=2;i<=n;i++)
   for（int j=2;j<=n;++j）
   {
      ++x;
      a[i][j]=x;
   }

在这个循环过程中，++x和a[i][j]=x是基本操作语句（for语句不算基本操作）.当i=2时，j执行n-1次；当i=2时，j执行n-1次......当i=n时，j依然执行n-1次。所以，f(n)=(n-1)*(n-1),只考虑最高阶，所以时间复杂度为O（n^2）。

for(int i=2;i<=n;i++)
   for（int j=2;j<=i-1;++j）
   {
      ++x;
      a[i][j]=x;
   }

在这个循环过程中，++x和a[i][j]=x是基本操作语句（for语句不算基本操作），但是注意，在第二个for语句中，表达式2是j<=i-1。在i变化的过程中，j的执行次数也在变，这个时候只能动笔算啦。

i=2,j执行0次；i=3,j执行1次;i=4,j执行2次......当i=n时，j执行n-2次。f(n)=2*(0+1+2+3+4+....+n-2)=n^2-3n+2,j执行n-1次。