No.60413427 - 科学
计算机导读从摇滚开始无名氏No.60413427 只看PO
2023-12-04(一)01:21:43
ID:22b93o1
这是一个从零开始的计算机学教程。教程里不会出现太过于深奥的内容，而是鼓励肥哥们根据串内的推荐自行学习。这个串只起到初步解释和导读的作用。
为了让计算机学更加有趣，也为了满足我的摇滚癖好，计算机和摇滚会在这个串里有机地结合起来，毕竟学习时听听音乐不也挺好嘛(ゝ∀･)
无标题无名氏No.60466973
2023-12-08(五)17:47:18 ID: 22b93o1 (PO主)
https://y.music.163.com/m/song/4336908
归并排序为何是合理的？为什么这种方法可以将列表从小到大排序？也许许多人已经感觉出来了它的正确性，但是算法不需要感觉，只需要证明。
归并排序由两段重复组成：重复的分解和重复的拼接。分解这个步骤仅提供拼接的顺序，或者说“分解”本身就是对于这种拼接顺序的解释。
我们将这种重复的拼接定义为一种循环（loop）。循环就是不停地做一件事，在这里就是不停地以排序的方式合二为一。在每一个循环中，所有小的列表被两两相拼，使其数量减半，长度翻倍（在假设列表长度是2的次方的情况下）。
在循环的时候，我们希望每个被拼接的列表保持一个特质，那就是它们都是有序的，是从小到大排列的。这种在循环中保持的特性被称为“循环不变式（loop invariant）”。
我们用数学归纳法（如果不知道这个是什么，请先自行了解数论基础，或者试着直接理解以下内容）看看循环不变式在循环中有没有被保持。
在拼接开始的时候，每一个列表仅有一个元素。一个元素的列表我们在这里默认已经从小到大排序，所以循环开始的时候所有列表是有序的。
在每一个循环中，一个列表由两个小列表拼接而成。拼接方式是比较列表中数的大小，大的摆后面，小的摆前面，如前文所叙述的一样。通过这种摆法，我们保证了没有大的数在小的数前面，即列表在循环后依然有序。
循环的结束条件是所有列表归一。因为列表在拼接后始终有序，最后所得的列表也是有序的。
论证完毕，循环不变式成立，循环后可以得到有序列表。
列表在每个循环中慢慢变好，Getting Better all the time。
无标题无名氏No.60639992
2023-12-25(一)00:23:38 ID: 22b93o1 (PO主)
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上，其他部分就显得可有可无了。