算法是什么

发表于2020-08-11更新于2023-01-10字数统计1.5k阅读时长9分阅读次数

算法

算法是用来干什么的？

算法是用来处理数据，解决问题的一组方法。对于同一个问题可以使用不同的算法来解决，但是其中消耗的时间和资源却可能不一样。

算法的优劣与否？

一般会通过算法的时间复杂度（程序耗时）和空间复杂度（程序所占用的内存）来衡量算法的优劣

时间复杂度

时间复杂度是什么？

时间复杂度用来反映程序的运行时间。常用的表示方法是大O表示法，即 T(n) = O(f(n))。可以通过下面的一段代码来解释下

1
2
3
4
for (i <- 1 until n){
    j = i
    j += 1
  }

在大O表示法中，f(n)表示每行代码的执行次数之和，O 表示正比例关系。所以上面的代码的时间复杂度就可以根据代码执行次数来看。for 循环执行n次，循环体里面的每行语句执行n次，所以执行次数是 3n，即时间复杂度是 O(3n)，当 n
无穷大时，就可以表示为 O(n)。下面介绍下常见的时间复杂度量级.

tip: 大O表示法主要用来表示程序的执行时间趋势，并不要求精准，因此上面的 O(3n) 可以变为 O(n)。

常数阶 O(1)

1
i = 1

i = 1 只执行一次，时间复杂度 O(1)

线性阶 O(n)

上面提到的单层 for 循环的时间复杂度就是 O(n)

对数阶 O(logN)

1
2
3
4
i = 1
while(i < n)
    i = i * 2

while 循环中，i 经过 log2n(2为底数)次大于 n 并结束循环。时间复杂度为 O(logN)

线性对数阶 O(n * logN)

就是 O(logN) 的代码循环执行了 n 次，比如下面的代码

1
2
3
4
5
6
7
for(i <- 1 until n)
{
    while(i < n)
    {
        i = i * 2;
    }
}

k次方阶

像 O(n2), O(n3), O(nK)

1
2
3
4
5
6
7
8
for(x <- 1 until n)
{
   for(i <- 1 until n)
    {
       j = i;
       j += 1;
    }
}

最好，最坏，平均情况时间复杂度

1
2
3
4
5
6
7
8
9
10
11
def find(seq:Seq[String], x:String) = {
    var pos = 0
    import scala.util.control.Breaks.{break, breakable}
    breakable {
        for(i <- 0 until seq.length){
            if (seq(i) == x){ pos = i; break }
        }
    }
    pos 
}

find 函数用来寻找指定元素在数组中的位置，时间复杂度是和数组的长度 n 有关。根据上面的讲解我们可以判定为 O(n)。但是事实上情况并不是这样，我们要找的数据元素可能在数组开头，数组结尾，甚至根本没有我们要找的东西。
对应种种不同情况，由此引出了最好，最坏，平均情况时间复杂度的概念。最好的情况是数据在数组开头，我们查找一次就可以，时间复杂度是 O(1)。最坏的情况我们遍历了整个数组才找到，时间复杂度是 O(n)。

find 函数的平均情况时间复杂度可以表示为查找需要遍历的平均数。要查找的变量 x 在序列 seq 中有 n+1 种情况：0~n-1个位置和不在序列中。假设查找值在序列中和不在序列中概率一样都为 1/2，数据出现在在任意位置上的概率为 1/n。
那么任意位置上查找到数据的概率是 1/2n。所以整体的复杂度计算为 11/2n + 21/2n + …. + n*1/2n + n * 1/2 = (3n+1) / 4 ，所以平均时间复杂度为O(n)

很多时候，我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。

平均时间复杂度经常需要考虑到概率，因此也叫加权平均时间复杂度

均摊时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var array = Array.ofDim[Int](10)
var len = 10
var i = 0
def add(a:Int) = {
    if(i >= len){
        var new_array = Array.ofDim[Int](len * 2)
        for (i <- 0 until len){
            new_array(i) = array(i)
        }
        array = new_array
        len = 2 * len
    }
    array(i) = a
    i = i + 1
    
}

下面分析一下上述函数的的均摊时间复杂度，一般用摊还分析(耗时操作均摊给给非耗时操作)的方法来分析，add 函数用于像数组中添加元素，每当达到数组长度上限时，将数组扩充 2 倍。
可以很容易看到，正常添加情况下，时间复杂度是 O(1)。只有当数组长度达到上限需要复制扩充时，时间复杂度为 O(array.len)。
调用10次，数组扩充到20，复制10次
调用10次，数组扩充到40，复制20次
调用20次，数组扩充到80，复制40次
不考虑第一次特殊情况，每次数组倍增之前，函数都会被调用n/2次，倍增时执行一轮n次拷贝操作。所以平均时间复杂度为 1/(n/2)*(n/2-1)+n/(n/2)
摊还分析，每一次O(n)操作后，都跟着n次O(1)操作，耗时操作均摊给给非耗时操作，就变成了常量级 O(1) 操作

空间复杂度

空间复杂度是程序运行时所占用的存储空间大小的量度，并非具体值，同样反映的也是趋势，用 S(n) 来表示。空间复杂度比较常用的有：O(1)、O(n)、O(n²)

1
2
3
4
5
6
var a = 1
a = a + 1
var array = Array.ofDim[Int](10)
for (i <- 0 until array.length){
    array(i) = i
}

a = 1，a 算法执行所需要的临时空间不随着某个变量n的大小而变化，空间复杂度为 O(1)。
第三行声明长度为10的数组，后面的循环不会对数组的空间产生变化，空间复杂度为 O(n)

使用搜索：谷歌必应百度