时间复杂度计算

时间复杂度

public void printsum(int count){
    int sum = 1;
    for(int i= 0; i<n; i++){
       sum += i;
    }
    System.out.print(sum);
}

记住，只有可运行的语句才会增加时间复杂度，因此，上面方法里的内容除了循环之外，其余的可运行语句的复杂度都是O(1)。
所以printsum的时间复杂度 = for的O(n)+O(1) = 忽略常量 = O(n)

这里其实可以运用公式 num = n(n+1)/2，对算法进行优化，改为

public void printsum(int count){
    int sum = 0;
    sum = count*(count+1)/2;
    System.out.print(sum);
}

这样算法的时间复杂度将由原来的O(n)降为O(1)，大大地提高了算法的性能。

操作数与输入数据的规模n比例为log2n

int i= 1;
while(i<n){
    i = i*2;
}

设(i=i*2)的频度是t, 则：2t(2的t次方)<=n; 两边去对数t<=log2n，考虑最坏情况，取最大值t=log2n。T(n) = O(log2n)。

如果a(a>0，且a≠1)的b次幂等于N，即ab=N，那么数b叫做以a为底N的对数，记作logaN=b（其中a叫做对数的底数，N叫做真数），这就是对数变换。 [1]

int num=0;
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        num++;
    }
}

时间复杂度为O(n^2)。

如果a^n=b,那么n=logab,a叫做底数，b叫做真数，n叫做以a为底b的对数，相应的，函数y=logaX叫做对数函数。
零和负数没有对数，底数a为常数，其取值范围是(0,1)U(1,∞)

在数据结构中，频度是指一个定义变量在它的函数中，并且是它在执行到该段语句为止时，这个定义变量在函数总共执行基本操作的次数。