Arts最近在自学好多东西呢…想发一些笔记出来…发点什么好呢？
偏数学或者计算机的都有呢…
4 个赞
似乎这里有好多oier？那Arts发计算理论的笔记怎么样呢qwq
Arts也想进行相关研究，所以会学得比较仔细认真的，也愿意花时间去整理总结
3 个赞
分析splay的复杂度当个开胃菜? x (超小声(被打死(((((((
以及有个子分区叫脱水菜, 这篇大概有资格放进去… ? (超小声(
ruarua搓搓的说 (超小声(
4 个赞
揉揉呢…计算理论的话…一般不会分析Splay的复杂度呢，不过既然被问到了，我就在这里手写一下吧
为了研究均摊复杂度，我们要为每个结点定义一个非负的函数（初始为0），将所有结点的这个值加起来视为一个数据结构整体的（非负）函数。这样一来，我们将每次操作的时间成本视为其真实的时间成本加整体末状态的函数值减整体初状态的函数值。也就是说，我们将这个函数视为“储蓄”，每一步可以积累一些储蓄（当这一步过于轻松时，我们视为花费了更多的时间，多花费的时间被存了起来留在以后使用），也可以消耗储蓄（当这一步过于复杂时，我们动用先前的储蓄来视为这一步仍然花费了较少的时间）
针对Splay，这个函数f在每个结点处定义为floor(log(以该结点为根的子树内结点个数))，我们经过推理可以证明，每次splay(x,y)操作，即在以y为根的树中将x旋转至根消耗的时间可以视为3(f(y)-f(x))+1。而f函数是log级别的，所有的其他操作又只会调用常数次splay操作，所以就都是均摊O(log n)复杂度啦
3 个赞
不过这个倒是可以视为笔记的一个风格参考，也就是说，我会省略一些不太值得关注的证明过程（比如那个3(f(y)-f(x))+1是怎么得到的，其实就是一个常规的分析过程），更多去关注整体思路。比如说，我会努力将各种概念解释清楚，以及讲述我们得到了哪些有价值的结论，它们之间的关系是怎样的；至于具体的证明过程，其实去翻书也不难查到。
我在学校听课时经常是老师花一节课去证明一个结论，而我由于没有理解基础概念（被老师一笔带过）而不知所云，看着一黑板正确的推理发呆。我希望这个笔记不仅能是自己思路的一个整理，也能够帮助到看到它的人吧
4 个赞
感觉写的不错（
每日新番 ×
4 个赞
qwq…(超小声)
3 个赞
再来更新一篇吧，这一篇很短，就是一些基础的数学知识。
1.pdf (164.7 KB)
下一节讲图灵机，不过更新可能就要很久以后了，因为之后每一章节都是有很多子章节的，内容很多。不过我不会忘了更新的
Eventually I will finish it!
1 个赞
oier当然是指参加过noi系列竞赛的人呢，不过这个笔记的话，感兴趣就来看好啦，大概计算机方向的人就有可能会需要学习这些（？）
1 个赞
揉揉，oi确实是青少年的竞赛，但是如果对算法竞赛有兴趣的话，还是有很多机会的啦
为何OI和数学的连接如此紧密，唉
我的逻辑思维其实还不错，但是数学就是糟心
其实不是数学糟心，只要涉及到计算我就糟心
也并不是算不出来，只是我完全没有耐心
也不是没有耐心，就是…我说不出来了
数学难吗，不难，其中的逻辑性其实还挺具有美感的
只要按照顺序一步步计算，有什么做不出来的呢
不过我就是做不出来，甚至高中物理和化学会涉及到的那一丁点完全是四则运算的计算我都讨厌的不行
甚至出现过物理选择题全对但是计算大题不想写的情况出现
选择题也需要计算，不过大部分题靠感觉其实也行
包括化学，计算个晶体密度啥的，都很容易，都是四则运算，把数据填进去按照方法一算就出来了，但是我就是讨厌的不行
不是不会做，而是刻意不想做
我数学不好，大概是心理阴影，主要是小学的数学老师太糟心了
偏偏OI里还是有这么多摆脱不掉的数学
比起抽象的算法，我更希望能搞点既和计算机相关又具象化图形化的东西
或许就算我真的接受系统的计算机竞赛教育我也不会取得多少成就的吧
或许，数字媒体艺术？
实际上我经常在steam壁纸引擎的创意工坊上传我自制的live2d动态壁纸
我寻思做个动画啥的也差不多吧
2 个赞
唉…
但是OI总不能去考深度学习吧
（或许也不是不行？但是可能这样的话很多考点的电脑配置就不行了）
其实我一开始真的以为OI就是去学计算机行业的前沿知识的
1 个赞
我看到 计算机 和 图形 的第一反应就是 算法 …
我学校有这门课，但是我没选
不然可以分享下读这门课的感受
2 个赞
这个倒不完全如此。复杂度衡量的是消耗的时间/空间的随问题规模增长而增长的趋势。应该说，恰是计算机的发明使得复杂度变得如此重要。因为随着计算能力的增长，我们可以解决更大规模的问题，此时常数部分的影响更为微弱，复杂度成为衡量算法效率的决定性因素。
3 个赞
Arts没有忘记这个主题哦！未来可能会视情况更新的呢
3 个赞