算法：基本概念

什么是算法？

算法解决某个特定问题步骤的描述。

算法的特性

1. 输入：可以是零个或者多个输入。
2. 输出：可以是一个或者多个输出。
3. 有穷性：无限循环肯定是不可以的。
4. 确定性：相同的输入，一定要得到相同的输出。
5. 可行性：每一步都必须在有限次数内完成。

算法的设计要求

1. 正确性：可以正确的解决问题
2. 可读性：方便阅读、理解和交流
3. 健壮性：输入不合法会做出相应的处理。
4. 效率高且存储量低。

算法效率的度量方法

算法的效率一般是指执行的时间。

事后统计法

对比多种算法的执行时间。

事前估算法

假如我们要求解1+2+3+···+100的和：

算法1:

    sum,n := 0,100              // 执行1次
    for i:=1; i<=n; i++ {       // 执行 n+1 次
        sum +=i                // 执行 n 次
    }

算法2:

sum, n := 0,100          // 执行 1 次
sum = n*(n+1)/2        // 执行 1 次

很显然算法一执行了2n+2次，算法二执行了2 次。忽略掉算法的第一行指令，也就是n次与1次的差别。

假设有一个算法3是下面的内容：

sum,n,m := 0,100,200
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            sum ++                // 执行了 n * n 次
        }
    }

我们通常在估算算法的效率时通常会忽略常数项，只是比较最高次幂。

比如说：算法A是 2n*n ，算法B是 3n+1，算法C 是 2n*n+3n+1。那么算法A的时间复杂度是O(n*n)，算法B的时间复杂度是O(n)，算法C的时间复杂度是O( n * n )

算法的时间复杂度

我们通常用O来表示算法的时间复杂度。
O(1) 通常称为：常数阶
O(n)通常称为：线性阶
O(n*n)通常称为：平方阶

我们通过例子来学习推导：

常数阶

sum, n := 0,100          // 执行 1 次
sum = n*(n+1)/2        // 执行 1 次

上面的代码执行了2次，但是我们通常会忽略常数项，把这段代码的时间复杂度计为O(1)。也就是我们说的常数阶，哪怕这段代码执行了10次，也是计为O(1)

线性阶

  sum,n := 0,100              // 执行1次
    for i:=1; i<=n; i++ {       // 执行 n+1 次
        sum +=i                // 执行 n 次
    }

在计算时间复杂度的时候，我们通常是忽略掉常数，并将最高次幂的常数项设为1，所以上述代码的时间复杂度为：O(n)。通常称为常数阶。

对数阶

   count, n :=1, 100

    for {
        if count > n {
            break
        }

        count = count * 2
    }

由于每次count乘以 2 之后就距离 n 更近一步了。2^x = n 所以 x = logn时间复杂度也就是为O(logn)

平方阶

sum,n,m := 0,100,200
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            sum ++                // 执行了 n * n 次
        }
    }

这段代码的时间复杂度为: O(n^2)

循环的时间复杂度等于循环体的复杂度乘以循环的次数。

时间复杂度消耗时间的顺序：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)