[数据结构与算法]算法及其时间复杂度

算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法 描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有 缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完 成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

常用算法

1.递推法

递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些 项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了 计算机速度快和不知疲倦的机器特点。

2.递归法

程序调用自身的编程技巧称为递归（recursion）。一个过程或函数在其定义或说明中有直接或间接调用自身的一 种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量 的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来 定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前 进；当边界条件满足时，递归返回。

注意：

(1) 递归就是在过程或函数里调用自身;

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

3.穷举法

穷举法，或称为暴力破解法，其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是 符合问题所要求的条件，从而得到问题的解。它也常用于对于密码的破译，即将密码进行逐个推算直到找出真正的 密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就 能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用 计算机来增加效率，有些人辅以字典来缩小密码组合的范围。

4.迭代法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解 法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算 法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指 令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

5.回溯法

回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先 选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个 状态的点称为“回溯点”。

其基本思想是，在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。 当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点 不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问 题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时， 只要搜索到问题的一个解就可以结束。

时间复杂度

假设计算机运行一行基础代码需要执行一次运算。

public int method(){

????????System.out.println("HelloWorld");

????????return 0;

}

那么上面这个方法需要执行 2 次运算

public int method(){

????????for(int i = 0;i<n;i++){

????????????????System.out.println("HelloWorld");

? ? ? ? }

? ? ? ? return0；

}

这个方法需要 (n + 1 + n + 1) = 2n + 2 次运算

把算法需要执行的运算次数 用 输入大小n 的函数 表示，即 T(n) 。 此时为了 估算算法需要的运行时间 和 简化 算法分析，我们引入时间复杂度的概念。

定义： 存在常数 c，使得当 N >= c 时 T(N) <= f(N)，表示为 T(n) = O(f(n)) 。

1. 我们知道常数项并不影响函数的增长速度，所以当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复 杂度为 O(1)；如果 T(n) 不等于一个常数项时，直接将常数项省略

第一个 Hello, World 的例子中 T(n) = 2，所以我们说那个函数(算法)的时间复杂度为 O(1)。 T(n) = n + 29，此时时间复杂度为 O(n)

2. 我们知道高次项对于函数的增长速度的影响是最大的。n^3 的增长速度是远超 n^2 的，同时 n^2 的增长速度 是远超 n 的。 同时因为要求的精度不高，所以我们直接忽略低此项。

例：T(n) = n^3 + n^2 + 29，此时时间复杂度为 O(n^3)。

3. 因为函数的阶数对函数的增长速度的影响是最显著的，所以我们忽略与最高阶相乘的常数。

T(n) = 3n^3，此时时间复杂度为 O(n^3)

综合起来：如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时 算法的时间复杂度就是 O(f(n))。为了方便描述，下文称此为 大O推导法。

由此可见，由执行次数 T(n) 得到时间复杂度并不困难，很多时候困难的是从算法通过分析和数学运算得到 T(n)。 对此，提供下列四个便利的法则，这些法则都是可以简单推导出来的，总结出来以便提高效率。

1. 对于一个循环，假设循环体的时间复杂度为 O(n)，循环次数为 m，则这个 循环的时间复杂度为 O(n×m)。

void method(){
    for(int i = 0;i<n;i++){ //循环次数为n
        System.out.println("HelloWorld"); //循环体时间复杂度为O(1)
    }
}

此时时间复杂度为 O(n × 1)，即 O(n) 。

2. 对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c...，则这个循环的时间复 杂度为 O(n×a×b×c...)。分析的时候应该由里向外分析这些循环。

void method(){
    for(int i = 0;i<n;i++){ //循环次数为n
        for(int j = 0;j<n;j++){ //循环次数为n
            System.out.println("Hello World"); //循环体时间复杂度为O(1)
        }
    }
}

此时时间复杂度为 O(n × n × 1)，即 O(n^2)。

3. 对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。

?

void method(){
    // 第一部分时间复杂度为 O(n^2)
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            System.out.println("Hello World");
        }
}
        // 第二部分时间复杂度为 O(n)
    for(int j = 0; j < n; j++) {
        System.out.println("Hello World");
    }
}

此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。

4. 对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。

void method(){
    if (n >= 0) {
    // 第一条路径时间复杂度为 O(n^2)
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            System.out.println("Hello World");
        }
    }
} else {
    // 第二条路径时间复杂度为 O(n)
    for(int j = 0; j < n; j++) {
        System.out.println("Hello World");
        }
    }
}

时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。