数据结构——时间复杂度

以前考计算机二级的时候了解过时间复杂度,但是没有专门研究过该如何计算,今天就总结一下时间复杂度的计算方法。
首先,我们看第一个例子:

int n=100;     //此处运行1次
for(int i=1; i<n; i++){     //此处运行n次
    System.out.println(i);  
}
该程序总共运行1+n次,那么该处的时间复杂度为多少呢?

接着,我们来看第二个例子:

int n=100;          //此处运行一次
for(int i=1; i<n; n++){  //该循环体总共运行n*n次
    for(int j=1; j<n; j++){
        System.out.println(i);
    }
}
该程序总共运行 n*n+1次,时间复杂度?    

上面两个例子中,随着n的增加,则式子中的常数项可以忽略不计。于是我们可以将n作为例一的时间复杂度,O(n)表示;将nn作为例二的时间复杂度,O(n*n)表示。

以下为推到时间复杂度的总结

  1. 用常数1取代运行时间中所有的加法常数。
  2. 在修改后的运行次数函数中,只保留最高阶项。
  3. 如果最高阶项存在且不是1,则去除与这个项相乘的常数。

评论

暂无评论