什么是算法

要学习算法的你，一定想要知道：到底什么是算法呢？

在前言部分我们大概提到，算法就是计算某个东西的方法。这是最直接、最简单也是最广泛的定义，但其实并不是很准确。

我们来看一个例子：高斯小时候在数学课上调皮捣蛋，他的数学老师罚他计算 1 加到 100 的和。高斯埋头开始计算，数学老师心里偷乐：这还不给你算到天荒地老！

此时，数学老师心中的计算方法是一个一个老老实实地挨个相加，也就是 $1 + 2 = 3$ ，然后 $3 + 3 = 6$ ，再然后 $6 + 4 = 10$ ……

用数学的语言表示就是这个样子的：

s = \sum\limits_{i = 1}^{100} i = 1 + 2 + \cdots + 100 = 5050

提示：关于数学语言

首先需要指出的是，你不需要完全理解每一个数学语言。

本书力求用通俗易懂且直观的方式展现算法的实现与背后的逻辑，而数学语言、严格定义等则是为了同时兼顾严谨性。为了满足某些读者对于严谨性的需求，本书会同时出现直观的语言和严谨的数学。对于大多数读者来说，你不需要完全理解本书中出现的数学语言。当然，如果能够理解自然是更好的。

然而，很快高斯就给出了他的答案：5050！

他的老师惊讶于他计算的速度，询问他计算的方法。高斯发现首尾总有能够从成一块的组合，它们的和是相等的：

\begin{cases} \begin{aligned} 1 + 100 &= 101 \\ 2 + 99 &= 101 \\ 3 + 98 &= 101 \\ \vdots \\ 50 + 51 &= 101 \end{aligned} \end{cases}

一共有多少组这样的组合呢？答案是 $100 \div 2 = 50$ 组。

所以，高斯的做法是：将 50 组的结果相乘即可。用数学的语言表示就是：

s = \sum\limits_{i = 1}^{100} i = 101 \times 50 = 5050

该方法后来经过推导和整理后，变成了大家耳熟能详的高斯公式，也叫等差数列求和公式、高斯算法等，就是大家常说的“首项加末项乘以项数除以二”，即：

s = \dfrac{\left(l + r\right) \times n}{2} = \dfrac{\left(l + r\right) \times \left(\dfrac{r - l}{k} + 1\right)}{2}

再次提醒

看不懂数学语言没关系，只要能够理解文字即可。数学语言是为了补充本书的严谨性。

上面这些式子，恐怕已经有人感到害怕了吧？其实不用害怕，算法与数学虽然有联系，但也不需要很高级的数学知识。你有初中的数学知识，基本就可以理解大部分内容了。

本书出现了数学语言的地方，基本上都会用通俗的自然语言再解释一遍，就像上文一样。

其中 $l$ 是首项， $r$ 是末项， $n$ 是项数， $k$ 是公差（也就是两个相邻的数的差）。

上面老师和高斯的计算方法都可以称作是算法，只不过高斯的算法更优。

我们可以把上面两个算法用代码实现出来：

private static int Teacher(int[] nums) {
    int res = 0;
    foreach (int num in nums) {
        res += num;
    }
    return res;
}

private static int Gauss(int[] nums) {
    int first = nums[0];
    int last = nums[^1];  // 取最后一个元素
    return (first + last) * nums.Length / 2;
}

fn teacher(nums: &[i32]) -> i32 {
    let mut res = 0;
    for num in nums {
        res += num;
    }
    res
}

fn gauss(nums: &[i32]) -> i32 {
    let first = nums[0];
    let last = nums[nums.len() - 1];
    (first + last) * (nums.len() as i32) / 2
}

当然，这里就没有再检查输入的序列到底是不是等差数列了。你可以设计额外的代码进行检查，这个应该很简单。

拓展：关于高斯的名字

我们很多人都知道高斯这个伟大的数学家，也有很多人知道他的英文名写作 Gauss。但提示一下，高斯是德国人哦！

高斯的德语名字写作：Gauß。这里有一个德语字母 “ß”，被称作“Eszett”或“Scharfes S”，在德语中用于表示清辅音 /s/。有趣的是，这个字母要跟在长元音后面，短元音后面使用“ss”。此外，2017 年，德语正字法协会引入了这个字母的大写形式 “ẞ”，但是大多数情况下人们还是使用“SS”来代替“ß”的大写哦。

这也说明了高斯的英语名写作 Gauss 是有依据的。

高斯的德语全名是：Johann Carl Friedrich Gauß

以上就是两种算法。两种算法虽然不一样，但是目的都是通过某种固定的方法得到问题的答案。因此，我们可以说，算法就是解决某个特定问题的答案的过程和方式。

让我们来看一下算法的准确定义：

定义：算法

算法（Algorithm） 是解决特定问题或执行特定任务的一系列明确的、有限的、可执行的步骤或指令的集合。算法具备一下特征：

获取输入：算法可以从外界输入数据并进行处理，也可以没有输入数据，简单地计算答案。
产生输出；算法要产生至少一个输出。不产生结果输出的算法是没有意义的。
确定性：算法解决问题的步骤或指令是确定的。
有限性：算法必须在有限的步骤或指令内解决问题或完成任务，不可以无限执行。
有效性：算法必须能够正确地解决问题或完成任务。

算法是一种理论性的概念，在研究算法的时候，我们通常会使用伪代码或代码进行算法的实现，自然语言和流程图当然也可以。算法只规定解决问题或执行任务的步骤或指令，而没有明确这些步骤或指令以什么样的形式展现出来。计算机算法最终都是要在计算机程序中执行的，所以伪代码、UML 流程图或实际代码是最常用的展现形式。本书将使用 C# 和 Rust 两种编程语言代码展现算法逻辑，必要时配 UML 流程图进行补充说明。

算法的效率

以上的两种算法：一种是老师的挨个做加法，另一种是高斯的分组算法。虽然两种算法都能够得到正确答案，但显然高斯的算法更加优秀、高效，尤其对于人手算而言。由此我们可以得出：

解决同一个问题的算法可能有很多种，但是有些算法非常低效，而有些算法则很高效。

实际应用中，我们需要根据问题选择合适的算法。对于需要快速编码、数据规模不大的问题，可以使用最朴素的做法，以减少代码和思维工作量；而对于需要长期使用、数据规模可能很大的问题，使用高效的做法是更好的选择。我们也能发现，对一个问题的特性进行分析，往往能够想到更好的算法。

而我们如何衡量一个算法在效率上的好坏呢？计算机中最重要的资源是运行时间和存储空间，也就是你的算法需要多久、要占用多少内存空间，而我们所讨论的计算机算法是在计算机上运行的，而算法具备有效性——正确的算法一定能解决问题，那么衡量算法好坏就有了两个标准：一个是在时间维度上的时间复杂度，而另一个是在空间维度上的空间复杂度。