本文最后更新于:星期一, 三月 16日 2020, 2:55 下午

什么是算法?

“算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。”
——摘录来自: 程杰. “大话数据结构。”

我个人理解,算法就是解决某一类问题的方法。我们的前辈总结了非常多优秀的算法,比如用于排序的冒泡排序、选择排序、插入排序算法,用于查找的二分查找、散列查找、顺序查找算法等。

为什么要学习算法?

  1. 算法是编程的基础,不管学习什么语言,算法早晚要学的,它是我们进阶到高级开发工程师所必须要掌握的知识之一。
  2. 可以培养自己写出高效的代码
  3. 锻炼自己的逻辑思维能力
  4. ~ 面试,找工作。🤦‍♂️

举一个简单的算法例子

大多数人都应该听说过著名数学家高斯的一个小故事:高斯在上小学的时候,老师布置了一个数学任务,让同学们对自然数从1到100求和。他很快就得出结果:5050。他的解释是这样的:

    num = 1 + 2 + 3 + ... + 99 + 100;
    num = 100 + 99 + ... + 3 + 2 + 1;
2 * num = 101 + 101 +... + 101 + 101; // 一共100个101相加
    num = 101 * 100 / 2 = 5050;

这道题如果用代码来实现的话,有两种解法:

  1. 普通解法
public int computeSum(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        sum += i;
    }
    return num;
}
  1. 高斯的解法
public int computeSum(int n) {
    int sum =  (1 + n) * n / 2;
    return num;
}

即使我们没有学过算法,我们也能看出来,这两种计算方法,第二种显然更加的高效,但是如果让我们来评价第二种算法有多高效,它的时间复杂度是多少,空间复杂度是多少,可能就需要我们了解一些算法的度量方法之后,才能准确的表达出来。


下面我们从算法的定义,特性,要求,度量方法来完整的了解一下算法

算法的定义

算法是描述解决问题的方法。算法(Algorithm)这个单词最早出现在波斯数学家阿勒·花刺子密在公元825年(相当于我们中国的唐朝时期)所写的《印度数字算术》中。如今普遍认可的对算法的定义是:算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。”

算法的特性

算法有五个基本特性:输入、输出、有穷性,确定性和可行性。

  1. 输入:待解决问题的条件,一般来说,一个算法会有一个或多个输入参数。(也可以是零个输入参数,如:打印hello world)
  2. 输出: 待解决问题的结果,输出的形式可能是打印控制台,或者返回一个数据。一个算法一定至少有一个输出。
  3. 有穷性: 指的是解决问题的步骤,必须是有限的。从我们写代码角度来理解的话,就是不能出现死循环。这个有限的步骤,也是有一定边界的,如果我们写了一个算法,需要一百年才能计算出结果,虽然说步骤可能是有限的,但是就算一百年不断电,一百年之后谁能验证这个结果是否正确呢😂,所以说这个“有限”,一定要合理。
  4. 确定性:相同的输入只能有唯一的结果,算法的每一步骤的意义都被精确定义而无歧义;
  5. 可行性:算法必须可以被实现。也就是说它每一步都必须可以转换为程序上机运行,并且得到正确结果。

算法的要求

评价一个算法是否有效,是不是够好,有四个指标:正确性、可读性、健壮性、时间效率高和存储量低.

  1. 正确性:这是一个算法最基本的条件,它指的是,算法至少应该根据问题的描述和输入,得到一个正确的输出。
  2. 可读性:算法设计的另一目的是为了便于阅读、理解和交流。(个人理解,这个指标的优先级在其他三个指标之后)
  3. 健壮性:当输入不合法的参数,我们要保证我们的算法可以正常执行,并返回结果,而不是直接程序报错。
  4. 时间效率高和存储量低: 这是评估一个算法是不是好的算法的指标,指的是这个算法执行的时间是不是足够短,消耗的内存是不是足够小。

总的来说,一个有效算法必须满足正确性和健壮性,如果同时能满足时间效率高和存储量低以及可读性,那么它就是一个有效的,并且是一个优秀的算法。

算法的度量方法

算法的度量方法有两种:1. 事后统计法;2. 事前估算法

事后统计法

事前统计法,主要是通过一批固定的测试数据,让不同算法的程序去执行,得到结果后,统计出不同算法的结果进行统计分析来判断不同算法的效率高低。
虽然这样也可以计算出算法的效率高低。但是它的缺点也很明显:

  • 硬件要求完全一致;
  • 测试数据设计困难,测试数据必须考虑的足够全面;
  • 如果算法比较复杂,这个统计的时间可能会需要很久;

所以一般来说,我们一般不考虑用这种方法来度量算法

事前估算法

先来看一下影响程序执行效率的因素:1.硬件;2.编译器;3.程序指令的执行次数;4.问题的条件和输入;
通过分析我们发现,第1,2,4个因素都是算法无法影响的,所以我们只关注程序代码,那么我们再回到上面那道题,计算1-100的和,我们看一下两种算法的程序代码

  1. 普通解法
public int computeSum(int n) {
    int sum = 0; //执行1次
    for (int i = 1; i < n; i++) { //int i = 1执行1次,i < n 执行 n 次,i++ 执行 n 次
        sum += i; //执行n次
    }
    return num;
}

整个程序代码一共执行了 1+1+n+n+n+n=4n+2次
2. 高斯的解法

public int computeSum(int n) {
    int sum =  (1 + n) * n / 2; // 执行1次
    return num;
}

整个程序代码一共执行了 1次

所以,显而易见,1 < 4n+2,第二种算法执行效率更高,第一种的时间复杂度,我们记作O(n),表示线性阶,第二种时间复杂度,我们计作O(1),表示常数阶;

算法的时间复杂度

“在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。
这样用大写O( )来体现算法时间复杂度的记法,我们称之为大O记法。一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法。”
——摘录来自: 程杰. “大话数据结构。”

简单理解,算法的时间复杂度和语句执行的次数紧密相关,如上面的提到的普通解法的算法执行次数:4n+2,我们用O(n)表示这个算法的时间复杂度。为什么不是O(4n+2),或者O(4n)? 接着看下面的推导大O阶的方法:

1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中,只保留最高阶项。
3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。取最高阶的项并忽略其常系数
——摘录来自: 程杰. “大话数据结构。”

接下来说为什么上面那个算法的执行次数是4n+2,但它的时间复杂度是O(n),
根据推导大O的方法1,可以得到 4n + 2 = O(4n + 1);
根据推导大O的方法2,只保留最高阶,4n + 2 =O(4n);
根据推导大O的方法3,最高阶项是4n,那么4n相乘的常熟是4,就需要除以4,最终结果是 4n + 2 = O(4n / 4) = O(n);

下面是常见的时间复杂度及例子

函数阶 非正式术语 执行次数的例子
O(1) 常数阶 1,2,12
O(n) 线性阶 4n+2,2n+1,n+10
O(n2) 平方阶 3n2+2n+1
O(logn) 对数阶 5log2n+20
O(nlogn) nlogn阶 2n+3nlog2n+19
O(n3) 立方阶 6n3+2n+3n+4
O(2n) 指数阶 2n
O(n!)
O(nn)

最后两种时间复杂度很少用到,常用的时间复杂度所耗费的时间从小到大依次是:
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

空间复杂度

“一般情况下,一个程序在机器上执行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为O(1)”
——摘录来自: 程杰. “大话数据结构。”

空间复杂度一般我们也用大O来表示,问题的输入、条件、输出变量取决于问题,所以不算做算法本身的存储空间,算法的存储空间只和其他的辅助变量有关。只要辅助变量的数量是常数,也就是说空间复杂度为O(1),那么这个算法就可以称为原地工作,原地工作这个词在leetcode题目中可能会出现。

对于算法的空间复杂度一般来说讲的比较少,计算机内存越来越大了,只要不是特别离谱,我们一般情况下,可能会故意通过空间来换时间,像系统设计中的缓存,就是很好的例子,所以空间复杂度我们大概了解就行,不过多在介绍了。

一张脑图概括

好了最后我们用一张图来总结一下这篇文章的内容

。。。
。。。
图片加载失败……
我只是困了想睡觉了🤦‍♂️


数据结构与算法      学习笔记 数据结构与算法

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!