No.60413427 - 科学
计算机导读从摇滚开始无名氏No.60413427 只看PO
2023-12-04(一)01:21:43
ID:22b93o1
这是一个从零开始的计算机学教程。教程里不会出现太过于深奥的内容，而是鼓励肥哥们根据串内的推荐自行学习。这个串只起到初步解释和导读的作用。
为了让计算机学更加有趣，也为了满足我的摇滚癖好，计算机和摇滚会在这个串里有机地结合起来，毕竟学习时听听音乐不也挺好嘛(ゝ∀･)
无标题无名氏No.60447359
2023-12-06(三)21:41:57 ID: 22b93o1 (PO主)
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.60460658
2023-12-08(五)01:05:03 ID: 22b93o1 (PO主)
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，感受一下无序是多么痛苦的一件事吧。