算法从入门到“放弃”（1）- 什么是算法？

写在开头

是什么让我萌生了写这系列文章的动力和想法呢？在大学课堂里学过入门算法，算法进阶等课程，还没接触前，就异常的兴奋，早就听说“算法”这种神秘的计算方法了，现在学校里教岂不美哉；等到学的时候，教授在上面讲，听得津津有味，感觉什么都懂了，回去自己写概念，实战的时候，又焉了；考试前，突击复习死记硬背了一遍，拿了个A，考完后，又基本都忘了。。。。
所以，面对这日后肯定经常使用的“工具”，不彻底理解肯定是不行的。唯有系统地全部梳理一遍才是良策。所以就有了写这系列文章的想法。
本系列文章都是自己在学习Thomas H. C 等作者所写的Introduction to Algorithms 第三版书，结合网上自己查阅的资料，所写下的一些感悟和想法。初入算法大门，希望大家不吝赐教。

什么是算法？

以下内容摘自维基百科，算法，Algorithm。

在数学和计算机科学中，一种算法是一个明确的关于如何解决一类问题的规范。算法可以执行计算，数据处理和自动推理任务。

作为一种有效的方法，算法可以在有限的空间和时间中表示，并在一个定义良好的正式语言中用于计算一个函数。从初始状态和初始输入开始（可能是空的），指令描述了一个计算，当执行时，通过一个有限的定义良好的连续状态，最终产生“输出”并在最终结束状态终止。从一个状态到另一个状态的转换并不一定是确定的; 一些算法，被称为随机算法，包含随机输入。

算法的概念已经存在了几个世纪，这个概念的使用可以归因于希腊数学家，例如Eratosthenes和欧几里德算法的筛子; 算法这个术语本身来自于9世纪的数学家muammad ibn msal’khwrizm。在1928年，大卫希尔伯特提出的解决“Entscheidungsproblem”（“决策问题”）的尝试，开始了对现代算法概念的部分形式化。随后的形式被框定为试图定义“有效的可计算性”或“有效方法”; 这些形式化包括了1930年、1934年和1935年的克莱伦递归函数、1936年的阿隆佐教堂的lambda微积分、1936年埃米尔波斯特的公式1和1936年的图灵机，以及1936年和1939年的图灵机。

自己的一些见解

就是更有效率地解决问题的计算方法。面对一个问题，先想出所有的解决方法，在其中找出一个最有效最简洁的方法的过程就是算法。

还记得课堂里有人问教授什么是算法，教授最后的解释就是一张图。

就是一个程序员不想解释他们做了什么的时候使用的名词 （笑）

本系列文章的前期准备

1. 如何评价算法的好坏？

最简单粗暴的方法，这个算法在限制的条件下是否解决了问题？
是，这是个可行的“好”算法，
不是，这是个不可行的差算法。
在这些可行的“好”算法中，是否有相对来说更好的？这就涉及到了比较，比较哪些东西呢？

平均时间复杂度；平均空间复杂度；最坏时间复杂度；最坏空间复杂度
输入与时间开销的分布关系；特定输入下的时间空间开销
所用的资源开销（如并行处理）；算法运行的特殊要求（如硬件支持）
通过这些东西来综合判断，不能一概而论。

———— 引用自在网上看到的@黄磊 在怎么评价一个算法的效率？问题中的问答。

我们这里仅考虑理论方面的时间复杂度。（空间复杂度很多时候不怎么关注，因为现在计算机硬件发展得很，算法中的数据存储基本是没问题的；很多时候我们甚至会“牺牲空间来换取时间”）

2. 引入渐近符号 asymptotic notation

那么如何比较时间复杂度呢？
Introduction to Algorithms 第三版书中引入了渐近符号这个概念。

We will use asymptotic notation primarily to describe the running times of algorithms. It actually applies to functions.

我们将使用渐近符号来主要表达算法的运行时间，这是运用在其中函数上的。
我们先假设有一个函数 g(n)。

2.1 Ө 符号

theta 符号
在这我们用Ө(g(n)) 来表示一组函数：Ө(g(n)) = {f(n): 任何大于0的常数 c1, c2, 和 n0 满足 0<=c1g(n)<=f(n)<=c2g(n)，对于所有的 n>=n0}.
我们说g(n) 是f(n) 的渐近紧范围 （asymptotically tight bound）。
因为Ө(g(n)) 的定义要求每个符合Ө(g(n)) 要求的f(n) 得是渐近不是负数的 (asymptotically non-negative)，也就是说，无论n 有多大，f(n) 都不会是负数。
函数g(n) 本身必须是渐近不是负数 (asymptotically non-negative) 或则集合Ө(g(n)) 是空集。

2.2 O 符号

O 大写符号
在这我们用O(g(n)) 来表示一组函数：
O(g(n)) = {f(n): 任何大于0的常数 c 和 n0 满足 0<=f(n)<=cg(n)，对于所有的 n>=n0}.
我们说g(n) 是f(n) 的渐近上范围 （asymptotically upper bound）。
注意：f(n)=Ө(g(n)) 说明了f(n)=O(g(n)) ，因为Ө 符号是个比O 符号强的符号；所以，我们可以说Ө(g(n)) ⊆ O(g(n))，Ө(g(n))是O(g(n)) 的子集。

2.3 Ω 符号

omega 大写符号
在这我们用Ω(g(n)) 来表示一组函数：
Ω(g(n)) = {f(n): 任何大于0的常数 c 和 n0 满足 0<=cg(n)<=f(n)，对于所有的 n>=n0}.
我们说g(n) 是f(n) 的渐近下范围 （asymptotically lower bound）。
这里说个理论，如果对任何两个函数f(n) 和 g(n)，仅且仅只有当f(n)=O(g(n)) 和f(n)=Ω(g(n))，我们会有Ө(g(n))。

2.4 o 符号

o 小写符号
在这我们用o(g(n)) 来表示一组函数：
o(g(n)) = {f(n): 任何大于0的常数 c，存在大于0的 n0 满足 0<=f(n)<cg(n)，对于所有的 n>=n0}.
我们说g(n) 是f(n) 的上范围但不是渐近紧 （upper bound that is not asymptotically tight）。
而且，在o 符号中，当n 越来越接近无穷大，函数f(n) 和g(n) 的关系会变得越来越无关紧要；也就是说，lim x → ∞ (f(n)/g(n)) = 0.

2.5 ω 符号

omega 小写符号
在这我们用ω(g(n)) 来表示一组函数：
ω(g(n)) = {f(n): 任何大于0的常数 c，存在大于0的 n0 满足 0<=cg(n)<f(n)，对于所有的 n>=n0}.
我们说g(n) 是f(n) 的下范围但不是渐近紧 （lower bound that is not asymptotically tight）。
而且，在o 符号中，当n 越来越接近无穷大，函数f(n) 和g(n) 的关系会变得越来越重要；也就是说，lim x → ∞ (f(n)/g(n)) = ∞.

3. 测试算法时间的程序

下面这段伪代码是以纳秒为单位计算的，可以在实际中相对准确地验证我们的理论时间。

// Java代码，测试程序运行的时间
// 伪代码 
long startTime=System.nanoTime();   // 获取开始的时间 
doSth();  // 算法内容 
long endTime=System.nanoTime(); // 获取结束的时间 
System.out.println("Running time of algorithm： " + (end-start) + "ns"); 

在下一篇文章中，将着重讲的是算法的重要基本内容，分而治之（divide-and-conquer）和3种解决递归问题的方法。

文章来源

来自2018年写的系列文章：https://zhuanlan.zhihu.com/p/40151536。