时间复杂度

两大词语

1. 算法效率

2. 时间复杂度

理解时间复杂度是什么之前，我们需要特别注意这两个词语。接下来就是一步一步的引入了。

1. 如何衡量一个算法的好坏

这串循环输出代码的算法好还是不好，为什么？我们该如何衡量算法的好坏？

public class Test {
    public static void main(String[] args) {
        int a = 0;
        while(a <= 5) {
            a++;
            System.out.println(a);
        }
    }
}

• 这里我们就要引入算法效率这个词语了

算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。

• 时间效率： 主要衡量的是 算法运行的速度
• 空间效率： 主要衡量的是 算法所需要的额外空间

时间复杂度

可以简单的理解为：算法的运行时间

概念：

1. 算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。

2. 一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

大O的渐进表示法

计算一下fun1基本操作执行了多少次？

void func1(int N){
    int count = 0;
    for (int i = 0; i < N ; i++) {
    for (int j = 0; j < N ; j++) {
    count++;
    }
}
    for (int k = 0; k < 2 * N ; k++) {
    count++;
    }
    int M = 10;
    while ((M--) > 0) {
    count++;
}

    System.out.println(count);
}

Func1 执行的基本操作次数 ：

为什么有时间复杂度？

3.算法的运行时间是算不出来的，只有运行起来才能知道，但是每个算法我们都运行显得麻烦。所以才有这个时间复杂度这个东西。

为什么我们不需要精确的计算？

1.太麻烦了

2.当N足够大的时候，我们就不会在意它后面是否加1了；不影响

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，

所以这里我们使用大O的渐进表示法。 大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法

1、用常数1取代运行时间中的所有加法常数。 （意思是去掉10）

2、在修改后的运行次数函数中，只保留最高阶项。 （意思是去掉2N）

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。 （意思是如果是3N^2,就去掉3）

所以使用大O的渐进表示法以后，Func1的时间复杂度为：

为什么默认所说的时间复杂度是最坏情况?

若算法的最坏情况--它的下限都比其他算法好的话， 那么它就被判定为一个特别好的算法了。所以我们只需要知道下限--最坏情况就好了。

有些算法的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

下列为常见的时间复杂度计算

• 例一

• 例二(嵌套for循环）

• 例三

• 例四(冒泡排序)

• 例五(二分查找)

• 例六(递归)

• 例七(斐波那契递归)