最高次项的指数大的，随着n的增长，结果也会变得增长特别快

算法函数中n最高次幂越小，算法效率越高

1.算法函数中的常数可以忽略；

2.算法函数中最高次幂的常数因子可以忽略；

3.算法函数中最高次幂越小，算法效率越高。

大O记法

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n的变化情况并确定T(n)的 量级。算法的时间复杂度，就是算法的时间量度，记作:T(n)=O(f(n))。

它表示随着问题规模n的增大，算法执行时间 的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度，其中f(n)是问题规模n的某个函数。

执行次数=执行时间

算法一：

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {

    int sum = 0;//执行1次

    int n=100;//执行1次

    sum = (n+1)*n/2;//执行1次

    System.out.println("sum="+sum);
}

算法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args) {

    int sum = 0;//执行1次

    int n=100;//执行1次

    for (int i = 1; i <= n; i++) {

    	sum += i;//执行了n次
    }

	System.out.println("sum=" + sum);

}

算法三：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {

    int sum=0;//执行1次

    int n=100;//执行1次

    for (int i = 1; i <=n ; i++) {

    	for (int j = 1; j <=n ; j++) {

     	sum+=i;//执行n^2次

    	}
    }
    System.out.println("sum="+sum);

}

**算法一：3次 **

**算法二：n+3次 **

算法三：n^2+2次

推导大O阶 的表示法

以下几个规则可以使用：

**1.用常数1取代运行时间中的所有加法常数； **

2.在修改后的运行次数中，只保留高阶项；

3.如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数；

所以，上述算法的大O记法分别为：

​ 算法一：O(1)

​ 算法二：O(n)

​ 算法三：O(n^2)

常见的大O阶

1.线性阶

一般含有非嵌套循环涉及线性阶，线性阶就是随着输入规模的扩大，对应计算次数呈直线增长，例如：

1
2
3
4
5
6
public static void main(String[] args) {
    int sum = 0;//执行1次
    int n=100;//执行1次
    sum = (n+1)*n/2;//执行1次
    System.out.println("sum="+sum);
}

上面这段代码，它的循环的时间复杂度为O(n),因为循环体中的代码需要执行n次

2.平方阶

一般嵌套循环属于这种时间复杂度

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
    int sum=0,n=100;
    for (int i = 1; i <=n ; i++) {
        for (int j = 1; j <=n ; j++) {
            sum+=i;
        }
    }
    System.out.println(sum);
}

上面这段代码，n=100，也就是说，外层循环每执行一次，内层循环就执行100次，那总共程序想要从这两个循环 中出来，就需要执行100100次，也就是n的平方次，所以*这段代码的时间复杂度是O(n^2).

3.立方阶

一般三层嵌套循环属于这种时间复杂度

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
    int x = 0, n = 100;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            for (int j = i; j <= n; j++) {
                x++;
            }
        }
    }
    System.out.println(x);
}

上面这段代码，n=100，也就是说，外层循环每执行一次，中间循环循环就执行100次，中间循环每执行一次，最 内层循环需要执行100次，那总共程序想要从这三个循环中出来，就需要执行100100100次，也就是n的立方，所 以这段代码的时间复杂度是O(n^3).

4.对数阶

1
2
3
4
5
int i=1,n=100;

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

由于每次i2之后，就距离n更近一步，假设有x个2相乘后大于n，则会退出循环。由于是2^x=n,得到x=log(2)n,所 以*这个循环的时间复杂度为O(logn); 对于对数阶，由于随着输入规模n的增大，不管底数为多少，他们的增长趋势是一样的，所以我们会忽略底数。

5.常数阶

一般不涉及循环操作的都是常数阶，因为它不会随着n的增长而增加操作次数。例如：

1
2
3
4
5
public static void main(String[] args) {
    int n=100;
    int i=n+2;
    System.out.println(i);
}

上述代码，不管输入规模n是多少，都执行2次，根据大O推导法则，常数用1来替换，所以上述代码的时间复杂度为O(1)

​ 0

他们的复杂程度从低到高依次为：

​ 0

所以，我们的算法，尽可能的追求的是O(1),O(logn),O(n),O(nlogn)这几种时间复杂度，而如果发现算法的时间复杂度为平方阶、 立方阶或者更复杂的，那我们可以分为这种算法是不可取的，需要优化。