( ｣ﾟДﾟ)｣＜X岛微信公众号已开放：【矛盾苇草】 官方微博：【X岛揭示板】

(;´Д`)为什么你发大红脸安全审核能通过而我不行

只能发大黄脸了

https://y.music.163.com/m/song/20045638

在介绍一个优美的好方法（并不是最好）之前，我们得先简单地了解一下算法界常用的，用于评估一个算法好不好的指标。

这个评估指标被称作复杂度。我们会根据算法在消耗时间，占用空间方面的大小和输入数据的大小的比例来判断这个算法好不好用。我们还会根据算法的最优表现（对于n个输入，理论最短结束的时间或最小花费的空间），最差表现和平均表现（期望值表现）来判断复杂度。

关于复杂度的定义，请参阅算法导论，我记得这本书的很前面就有这个定义。

在你了解什么是复杂度之后，我会简单地介绍什么是数据类型和数据结构。

对于计算机来说，一切都是0和1的数据，正如对世界来说，一切都是基本粒子。

但是粒子的组合也有不同的性状，例如常温下是液体的水和常温下是固体的铁是不一样的。数据亦然。数据的性状由其用途分类。根据用途不同，我们可以分出类似于这些的数据类型：

- 整数（int）：可以用于表示“个数”
- 布尔值（boolean）：仅有两种布尔值：正确与错误，用于表示“是否”的判断
- 字符（char）：单个的字符，如“a”或者“♡”，一般来说算法中仅考虑英文字符就足够了。字符本质上是一个代表了字符的数字（想想二进制代表不同肢体的例子）
- 列表（array）：一个收纳了单个或多个数据类型的数据的集合，根据用途不同，定义不同。例如前文的“9，5，2，7”就是一个只存放整数的列表。列表中的每一个东西被称为它的元素（element）。在某些编程语言的定义下，列表甚至可以有无限个元素，但同一时间只能取出有限个元素
- 字符串（string）：仅存放字符的列表。
...

对于上述数据类型中的每一个，我们都有一些独特的操作。例如对于整数，我们可以加减乘除；对于列表，我们可以增加元素，修改元素，删除元素，引用元素（即获取一个元素的值）等。

也正像我们可以通过创造工具的方式利用外物来代替自身来作业，我们可以赋予数据类型特殊的意义，以使其成为一种稳定的结构，即数据结构。这种结构有两个作用：

>方便我们使用
包括方便我们可视化，理解，提出相关理论，分析，利用和转化。

>作为算法的前提
一些算法可以简单地解决难题，是因为其输入是一种稳定的，有可以被利用的独特性质的数据结构。

事实上，一些睿智的学者甚至证明了某些应用于不同数据结构的难题可以互相转化（reduction）。PNP问题的提出就利用到了一些转化。

数据结构需要维护。当数据结构发生变化的时候，我们需要进行一些操作来使其性质不发生变化，就像你不能把随便什么东西随意扔在你的桌子上，然后声称它还是被整理好的桌子。

接下来的排序算法中，我用到“列表”这种数据类型，和“被排序好的列表”这种数据结构。

听一听Discipline，它会让你感受到变化与秩序的伟力。

https://y.music.163.com/m/song/20045638

在介绍一个优美的好方法（并不是最好）之前，我们得先简单地了解一下算法界常用的，用于评估一个算法好不好的指标。

这个评估指标被称作复杂度。我们会根据算法在消耗时间，占用空间方面的大小和输入数据的大小的比例来判断这个算法好不好用。我们还会根据算法的最优表现（对于n个输入，理论最短结束的时间或最小花费的空间），最差表现和平均表现（期望值表现）来判断复杂度。

关于复杂度的定义，请参阅算法导论，我记得这本书的很前面就有这个定义。

在你了解什么是复杂度之后，我会简单地介绍什么是数据类型和数据结构。

对于计算机来说，一切都是0和1的数据，正如对世界来说，一切都是基本粒子。

但是粒子的组合也有不同的性状，例如常温下是液体的水和常温下是固体的铁是不一样的。数据亦然。数据的性状由其用途分类。根据用途不同，我们可以分出类似于这些的数据类型：

- 整数（int）：可以用于表示“个数”
- 布尔值（boolean）：仅有两种布尔值：正确与错误，用于表示“是否”的判断
- 字符（char）：单个的字符，如“a”或者“♡”，一般来说算法中仅考虑英文字符就足够了。字符本质上是一个代表了字符的数字（想想二进制代表不同肢体的例子）
- 列表（array）：一个收纳了单个或多个数据类型的数据的集合，根据用途不同，定义不同。例如前文的“9，5，2，7”就是一个只存放整数的列表。列表中的每一个东西被称为它的元素（element）。在某些编程语言的定义下，列表甚至可以有无限个元素，但同一时间只能取出有限个元素
- 字符串（string）：仅存放字符的列表。
...

对于上述数据类型中的每一个，我们都有一些独特的操作。例如对于整数，我们可以加减乘除；对于列表，我们可以增加元素，修改元素，删除元素，引用元素（即获取一个元素的值）等。

也正像我们可以通过创造工具的方式利用外物来代替自身来作业，我们可以赋予数据类型特殊的意义，以使其成为一种稳定的结构，即数据结构。这种结构有两个作用：

>方便我们使用
包括方便我们可视化，理解，提出相关理论，分析，利用和转化。

>作为算法的前提
一些算法可以简单地解决难题，是因为其输入是一种稳定的，有可以被利用的独特性质的数据结构。

事实上，一些睿智的学者甚至证明了某些应用于不同数据结构的难题可以互相转化（reduction）。PNP问题的提出就利用到了一些转化。

数据结构需要维护。当数据结构发生变化的时候，我们需要进行一些操作来使其性质不发生变化，就像你不能把随便什么东西随意扔在你的桌子上，然后声称它还是被整理好的桌子。

接下来的排序算法中，我用到“列表”这种数据类型，和“被排序好的列表”这种数据结构。

听一听Discipline，它会让你感受到变化与秩序的伟力。

>>No.60447359
说实话，关于数据结构和数据类型的定义我有些记不清了，如果有问题的话请告诉我，非常感谢

(*ﾟーﾟ)

ﾟ∀ﾟ)σ[订阅]

https://y.music.163.com/m/song/18860373

那么，我开始介绍归并排序（Mergesort），包括其算法的运作机制，原理，具体实现，改进方案，复杂度与缺点。

首先，为了普适性，我们拿的例子是一个仅包含数字的列表：[1.0, 3.1, 2.5, 5.6, 0.7]。

“[”代表列表的开始，“]”代表其结束，其中每一个被逗号分割的数字都是一个该列表的元素。

归并排序的运行机制如下：
将列表从中间切开，分成两个列表[1.0, 3.1]与[2.5, 5.6, 0.7]（如果为奇数，我们在这里默认切成(n-1)/2和(n+1)/2的长度，反过来也不会有什么影响）。

为了方便表示，我们写作[1.0, 3.1/2.5, 5.6, 0.7]表示我们在“/”的地方切了一次，分成了两份。

对每个切开后的列表再次切开，例如[1.0, 3.1]将变为[1.0]和[3.1]（注意，[1.0]并不是1.0，前者是含一个元素的列表，后者是一个数字）。

像这样，每次一切为二，在经过三次切割后可得[1.0/3.1/2.5/5.6/0.7]。

这是归并排序的第一步，分开。对于长度为n（含n个元素）的列表，需要花费的时间为lg(n)，其中lg为以2为底的log（不知道什么是log？请自行学习对数）。

分久必合，下一步是合。

在最后一次切割结束后，对于每一轮切割过后的两半，将这两半合起来，以一个保证其从小到大排列的方式。

什么意思？我们还是看刚才的例子。

在最后一轮中，[5.6, 0.7]被拆分为[5.6]，[0.7]。现在我们想以从大到小排列的顺序来合并这两个数，方法很简单：比较一次5.6，0.7的大小。0.7小，所以0.7排前面，5.6排后面，两个列表合并为[0.7，5.6]。

在倒数第二轮（也就是第二轮）中，[2.5]和[5.6, 0.7]被拆分开来。因为我们已经将[5.6, 0.7]在拆分后有序组合，使其变为[0.7, 5.6]，我们需要让2.5先和[0.7, 5.6]中的第一个数0.7比，比0.7大之后再和5.6比。比5.6小，则排5.6前面，变为[0.7, 2.5, 5.6]。

同理，[1.0, 3.1]和[0.7, 2.5, 5.6]比。1.0大于0.7小于2.5，则排在两者之间。3.1因为在1.0后，而0.7小于1.0，所以3.1必定大于0.7，从2.5开始比。比2.5大，比5.6小，所以排两者之间。

列表被排序完成。

被排序的列表带来了秩序。秩序的作用会在下文中提到，在其原理之后，在具体实现之前，但是我们可以先听听Disorder，感受一下无序是多么痛苦的一件事吧。

>>No.60460658
为了普适性的意思是我不只用整数。但实际上，因为和数字有关的操作只有比较大小，用整数和浮点数（就是小数）是一样的

https://y.music.163.com/m/song/4336908

归并排序为何是合理的？为什么这种方法可以将列表从小到大排序？也许许多人已经感觉出来了它的正确性，但是算法不需要感觉，只需要证明。

归并排序由两段重复组成：重复的分解和重复的拼接。分解这个步骤仅提供拼接的顺序，或者说“分解”本身就是对于这种拼接顺序的解释。

我们将这种重复的拼接定义为一种循环（loop）。循环就是不停地做一件事，在这里就是不停地以排序的方式合二为一。在每一个循环中，所有小的列表被两两相拼，使其数量减半，长度翻倍（在假设列表长度是2的次方的情况下）。

在循环的时候，我们希望每个被拼接的列表保持一个特质，那就是它们都是有序的，是从小到大排列的。这种在循环中保持的特性被称为“循环不变式（loop invariant）”。

我们用数学归纳法（如果不知道这个是什么，请先自行了解数论基础，或者试着直接理解以下内容）看看循环不变式在循环中有没有被保持。

在拼接开始的时候，每一个列表仅有一个元素。一个元素的列表我们在这里默认已经从小到大排序，所以循环开始的时候所有列表是有序的。

在每一个循环中，一个列表由两个小列表拼接而成。拼接方式是比较列表中数的大小，大的摆后面，小的摆前面，如前文所叙述的一样。通过这种摆法，我们保证了没有大的数在小的数前面，即列表在循环后依然有序。

循环的结束条件是所有列表归一。因为列表在拼接后始终有序，最后所得的列表也是有序的。

论证完毕，循环不变式成立，循环后可以得到有序列表。

列表在每个循环中慢慢变好，Getting Better all the time。

在每个循环中，我们以算法所规定的方式“维护”了循环不变式，使其保持而不是消失，而这个循环不变式保证了最后所得列表有序。

这种“维护”和对于数据结构的维护在本质上是一致的——利用某种方法来保证某一有用性质不消失。

保持性质不变的思想(*´∀`) 好棒

>>No.60460658
毕业两年竟然看归并排序都陌生起来了(;´Д`)
不过po配joy division感觉很妙|∀` )

喜欢po的语言风格，摩多摩多！

http://music.163.com/album/2064268/

接下来，我会讲为什么我们要排序。

除了符合我们人类对于秩序的喜好外，一个排序的列表最大的特点是便于搜索。

在这里，搜索特指这个问题：输入一个数字n和一个列表l，能否从列表中找到一个元素的索引i，使该元素（标为l[i]，指代位于列表第i-1个的元素）和给定的数字n相等。如果列表中不存在和这个数字相等的元素，则输出-1以表示列表中没有匹配元素。

可以理解为，在一个图书馆（列表）里找到想要的书（数字）。

一个列表可以有重复的数字元素，输入的数字可能匹配到多个元素，此时只要找到任意一个对应元素所在的索引即可。

这里稍微谈谈索引的概念：元素在这个列表中从左到右排第N个，索引即为N-1。

或者我们可以这样理解：对于[1, 4, 1, 4]这个列表，l0[0,0]指代1，l1[0,1]为4，l2[0,2]为1，l2[0,3]为4。

为什么从0开始为列表中的元素标索引？现在我的解释是因为索引在计算机中也表示成二进制数字，而0000 0000显然比0000 0001更适合作为索引的开始。我们之后会从储存地址的角度做更严谨的解释。

我们现在使用的列表储存的都是数字，接下来可能会储存“不可能一样”的数据类型或者“用途一样，但储存在不同地方”的数据类型，在谈地址的时候也会更明确地谈论这一点。

搜索问题定义完成，我们继续谈论如何搜索。首先我们先看看对于一个无法通过前N项元素推断出第N+1项元素有何性质的列表（注意，这个定义比“随机数字”更加广泛和固定，我们可以不知道X岛的下一条回复是什么，但这个回复不会是根据某种分布随机生成的数字）来说该如何搜索。

最简单，最合适，最保守的搜索方式是从列表的第0个元素开始（从这里开始我们从索引的角度描述列表），将每个元素和输入的数字n比对。如果一样，就结束算法，输出目前元素所在的索引，如果不一样就比对下一个。这个索引可以通过保持一个变量，每搜索一次就进一位（increment）的方式维护。这是最初级的循环不变式：我们维护的这个变量在循环中一定等于目前比对过元素的索引。如果比对所有元素但没有输出过数字，则输出-1，因为全对比了也找不到匹配元素。

我们评估一下这种算法。在最差（即需要进行最多运算）的情况下，我们需要O(n)的时间复杂度来输出一个-1或者最后一个索引。不知道时间复杂度的，还是建议看算法导论或其他教程。

在最优情况下，我们只需要进行一次对比即可，时间复杂度为O(1)。

我们再从搜索空间（search space）的角度来看。搜索空间即答案可能处于的集合。换句话说，就是列表中可能和输入数字相等的元素。

在没有比对的时候，任何列表中的元素都有可能是我们想要的那个，但是我们不知道。此时搜索空间等同于列表。

在我们对比的过程中，我们确定了一些元素不可能和输入数字相等，那么搜索空间的大小就变小了，我们只需要从更小的空间中搜索元素了。当搜索空间为0，即没有元素的时候，我们一定能得到一个结果：这个空的搜索空间中不可能存在我们想要搜索到的元素。

在我们提到的一个个去对比的算法中，搜索空间在每一次对比后被删除一个元素，因为对比后我们知道这个元素不可能是结果（或者就是结果，那么我们可以直接结束算法）。初始搜索空间大小为n，每一次对比必定使大小减一。在越来越狭小的空间里，我们可以越来越逼近答案。

Hawkwind的In Search of Space专辑让我迷醉：一点太空，一点迷幻，一点硬摇滚。冷淡高傲的嗓音，宇宙般无处不在，平淡却宏伟的bassline，在深沉幻想中拨动的吉他riff，并不刻意去愉悦或者折磨耳朵的合成音，我不敢相信身处他们的live中该有多震撼。

专辑封面不能忘

https://y.music.163.com/m/song/22448942

对于一个从小到大排序的列表来说，我们有更好的方式来搜索这个列表：首先将要搜的数字n与列表最中间的第x/2个元素做比较，x为列表长度，即其所包含的元素个数（推荐没有接触过这种算法的读者先自行拟一个列表试一试下面的算法，可以让你快速理解那些让人头大但不得不写的原理阐述）。

如果n比这个元素小，则证明n在列表的第零个元素到第x/2-1个元素之间，因为这些元素小于等于第x/2个元素，而第x/2个元素大于n，换句话说，第x/2+1到第x个元素不可能存在n，因为n<第x/2个元素<第x/2+1和之后的元素；如果n比这个元素大，则n在第x/2+1到第x个元素之间。

如果n和第x/2个元素一样大...那我们已经找到了结果。

简而言之，对于目前的列表，将n与中间元素作比较，然后要么得到结果，要么抛去一半的列表得到新的“目前的列表”，不断重复直到得到结果。

这个算法叫二分算法（binary search），或者说折半算法。每一次比较，我们都可以将搜索空间减半，抛去一半必然不可能存在结果的元素。其时间复杂度为O(log(x))（这是什么意思？请自行参照书本）。

顺带一提，在这里，我们可以初步看到离散数学和连续数学的区别。对于一段数轴来说，你不可能通过这个算法在有限的时间内找到一个无理数，因为“日取其半，万世不竭”（为什么？提示：在数轴上随机选中任意数的可能性为0）；而对于一个存在有限个数字的列表来说，你可以将搜索空间不断折半，缩小到1，然后通过最后一次对比判断n是否在列表中，是否需要输出-1。

列表这个数据类型的特性是“读取列表中任意索引的元素都只需要固定的常数时间”，提取第0个元素和第x/2个元素消耗都是固定的，这也是支撑二分搜索时间复杂度为O(log(x))的前提条件。如果提取第x/2个元素需要一路扫过去，消耗时间大于提取第0个元素，这个算法就不是那么有效了。

为什么我们假设列表具有这样的特性？因为我们在现实中可以利用数据磁盘来做到几乎相同时间的读取，与列表性质吻合，所以这种假设所得的算法对于数据磁盘上的数据操作是有用的。“列表这种数据类型在现实中有用”的证明就涉及到计算机硬件了。

抛去不必要的东西这件事，本身就很有必要。就像Afraid to Shoot Strangers这首歌，精髓全在两段solo上，其他部分就显得可有可无了。

>>No.60639992
这一段的“数轴”，特指开始和结尾为有理数的数轴

>计算机摇滚串
>串首的大红脸
>对味了(ゝ∀･)

催更！(=ﾟωﾟ)=