当前位置 博文首页 > Vicky_2020的博客:数据结构——时间复杂度
以前考计算机二级的时候了解过时间复杂度,但是没有专门研究过该如何计算,今天就总结一下时间复杂度的计算方法。
首先,我们看第一个例子:
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++){ //该循环体总共运行nn次
for(int j=1; j<n; j++){
System.out.println(i);
}
}
该程序总共运行 nn+1次,时间复杂度?
上面两个例子中,随着n的增加,则式子中的常数项可以忽略不计。于是我们可以将n作为例一的时间复杂度,O(n)表示;将nn作为例二的时间复杂度,O(n*n)表示。
以下为推到时间复杂度的总结