时间复杂度的计算

如果我们想验证一段代码的效率，一个最直接的办法就是编出来之后运行一下，这个方法称为事后统计方法，但是这个方法存在着非常大的弊端，比如我们需要时间编写代码，而代码写完后如果不符合要求需要重新编写；测试的方法会受到硬件和内存占有率的影响等等。所以为了让代码的评估更加规范和科学，我们更多的使用事前分析估计方法，即计算一个代码的时间复杂度。 其实一段代码的时间复杂度计算很容易，它是一种对计算次数的统计，它有如下几条规则： 1.用常数1取代运算次数中所有的加法常数。 2.只保留最高阶的项。 3.将最高阶的项前面的系数换成1. 这个方法被称之为大O阶方法。 我们通过几个例子看一看上述规则到底如何让使用：

int  sunm =0,n=100;    //执行1次
sum= (1+n)*n/2;        //执行1次
printf("%d",sum);      //执行1次

上面一段代码一共执行3次，但是时间复杂度是O(3)吗，按照规则1，上述代码的时间复杂度应该是O(1)。

int i;                  //执行1次
for (i = 0;i<n;i++)     //执行n+1次
{
  printf("%d",i);       //执行n次
}

上面一段代码一共执行2n+2次，按照大O阶方法： 2n+2——2n+1 2n+1——2n 2n——n 上述代码的时间复杂度应该是O(n)。

int i,j;                //执行1次
for (i = 0;i<n;i++)     //执行n+1次
{
    for (j = 0;j<n;i++) //执行n+1次
    {
        printf("%d",i);   //执行n*n次
    }   
}

上面一段代码一共执行n*n+2n+3次，按照大O阶方法： n*n+2n+3——n*n+2n+1 n*n+2n+1——n*n 上述代码的时间复杂度应该是

这里写图片描述

。

int i,j;                //执行1次
for (i = 0;i<n;i++)     //执行n+1次
{
    for (j = 0;j<m;i++) //执行n+1次
    {
        printf("%d",i);   //执行n*m次
    }   
}

上面一段代码一共执行mn+2n+3次，按照大O阶方法： mn+2n+3——n*n+2n+1 mn+2n+1——mn 上述代码的时间复杂度应该是O(m*n)

int count = 1;     //执行1次
while(count<n)   //执行k+1次
{
    count = count*2;  //执行k次
}

这里写图片描述

上述代码的时间复杂度应该是

这里写图片描述

最后给出常见的执行次数函数与其对应的时间复杂度：

这里写图片描述

常见时间复杂度排序：

这里写图片描述