JAV 是吧
你怎么知道今晚准备打交 
。
jav 很好，cs61b proj0 也很好，赞美啊！
唉，之前我还计划着学 java 来着，这几天都看小说 + 学数学
，下周我们数据结构就开始了 现在 
Java 还没入门
数学领域大神 
。
好好，我宣布成立胶带门数据结构学习小组，狠狠学习 。
好好好
狠狠加入大神的学习小组 
学习小组有了，大神在哪
这是 Autograder 的 Halloween 彩蛋吗 
，刚看到还被吓到了。
ASAG: If you are looking for ransom, I can tell you I don't have money. But what
I do have are a very particular set of skills; skills I have acquired over a
very long career. Skills that make me a nightmare for people like you. If you
let my daughter go now, that'll be the end of it. I will not look for you, I
will not pursue you. But if you don't, I will look for you, I will find you and
I will give you a zero.
2023-10-31T10:24:00Z
做完了 cs61b proj1a。第一次用 Java 写双向队列，过程中还是遇到了些问题的。使用了 resizing-array 和 DLList 两种数据结构实现，还使用 jUnit 写了 unit test。（虽然还是没搞懂 vscode 怎么检测 Java project 的，不能直接在 vscode 中启动测试）
修完 bug 提交后，用完了三次提交资格，但还有 style 的 2.5 分没拿到。是 hidden field error，其实是命名的问题。我在 class 中调用成员变量和函数都 explicitly 使用了 this，所以其实没大碍。
顺便，还看到了今天 Autograder 的一个彩蛋，还稍稍被吓到了点 
。
明天就 11 月了啊，天气也是越来越冷了，我也该加快速度了。Searching 部分的树和二叉树学过了，但还没有实现过，快速过一遍就开始上手。Sorting 部分的书还得看。还要做一下 proj1b。
2 Likes
Autograder score: 50.0 / 50.0
ASAG: Because your code deserves the best
好 。
好耶
1 Like
2023-11-01T19:10:00Z
cs61b proj1b 堂堂完成！这节主要是应用之前 proj1a 中编写的 deque 数据结构，简单的。
3 Likes
2023-11-06T12:40:00Z
讲得太好了！ Sedgewick 为什么是神：
排序算法部分先给出了最简单、符合直觉的 Selection sort 和 Insertion sort。这两种算法复杂度都是 O(N^{2}) ，但是 Insertion 要略快一些。
在 Insertion 的基础上进行优化，先把每隔 h 个元素的子数列排序好（h-sorted），再减小 h 的值直到 1。这样使得每个元素首先抵达自己目的地附近的位置，减少交换的次数。如此得到了 Shellsort，虽然不能证明其复杂度，但是 it’s complexity is not necessarily \sim N^{2} 。
Mergesort 是将数列切分成两个字数列，分别排序好后再进行合并。可以使用递归的 Top-down mergesort，也可以使用非递归的 Bottom-up mergesort。
递归的 divide and conquer 思想与数学归纳法相对应，于是可以用 Induction 来证明其复杂度为 \sim N \log N 。作者也使用二叉树证明了任何基于比较的排序方法，其复杂度都不可能比 N \log N 更优。（这段证明看得本 
是浑身喜悦，接近高潮）
虽然 Mergesort 已经是 asymptotically optimal，但是其使用了辅助数列，所以空间复杂度不是最优。书中也给出了几个小优化点，可以在常数层面上进行优化。
在工程中应该永远首先使用最简单直观的方式，只有在这个算法成为 bottleneck 的时候再去优化它。
-
Fundamentals
-
Sorting
- Elementary sorts
- Mergesort
- Quicksort ←
- Priority queues
- Applications
-
Searching
-
Graphs
-
Strings
-
Context
老哥买的英文原版啊，应该很贵吧…
不是进口的，是人民邮电出版社和中国工信出版集团在大陆出版的。定价是 129，当时买的应该能稍微便宜一点。
2023-11-07T13:50:00Z
Quicksort 与 mergesort 相比，不用创建辅助数组，因此空间占用更少。精细调整后的 quicksort 还可以将复杂度由 \sim N\log N 降低到 \sim NH - N ，其中 H 为 Shannon 熵。对于存在大量重复 key 的数组，复杂度甚至可以达到 linear。
-
Fundamentals
-
Sorting
- Elementary sorts
- Mergesort
- Quicksort
- Priority queues ←
- Applications
-
Searching
-
Graphs
-
Strings
-
Context
1 Like
书好像开胶了 ，有点心疼 
这个可以和哈夫曼编码一块看
这个书上写的是前面那个结论的直接推论吗？