我是一位高中信息学竞赛选手。我们首先需要掌握基础结构(顺序,循环,分支),然后开始由浅入深地学习算法。
举一个例子:你需要在 0.01s 内,从 100 个元素中找到指定的一个。怎么写?
答:顺序结构,直接枚举。
第二个例子:你需要在 0.01s 内,从 1000000 个元素中找到指定的一个。怎么写?
答:我也不知道。
第三个例子:从 1000000 个元素中找到指定的一个叫做“单位操作”。保证数据是冷的,你需要执行 1000000 次“单位操作”,总共给你 1 秒钟,怎么写?
答:$Theta(N log N)$排个序,然后二分查找。总时间复杂度$Theta(N log N)$
第四个例子:从若干个元素中找到指定的一个叫做“单位操作”。但是这回不保证数据是冷的,也就是随时可能新加进来一个元素,或者被删除一个元素。每一次加入的元素是随机的,数据库中最多 1000000 个元素。你需要执行 1000000 次“单位操作”,总共给你 1 秒钟,怎么写?
答:维护一个二叉排序树。由于数据随机,期望树高是$O(log N)$级别的。总时间复杂度$Theta(N log N)$
第五个例子:从若干个元素中找到指定的一个叫做“单位操作”。这回依然不保证数据是冷的,也就是随时可能新加进来一个元素,或者被删除一个元素。这回不保证每一次加入的元素是随机的,数据可能很恶心,数据库中最多 1000000 个元素。你需要执行 1000000 次“单位操作”,总共给你 1 秒钟,怎么写?
答:由于数据不随机,期望树高退化到$O(N)$级别的。我们需要使用 FHQ Treap (或者随便一个平衡树)来实现随机化。期望树高变回$O(log N)$级别,总时间复杂度$Theta(N log N)$。
——–扯淡完毕——–
5 个例子中,第一个:5 行代码解决。第二个:我也不知道。第三个:15 行代码。第四个:30 行代码。第五个:60 行代码。(均指使用 c++实现程序的代码核心部分长度)
在我的理解中,这 4 个功能,难度越来越难,需求越来越大,越来越考验水平。如果按工时计费,你拿的钱越来越多。但是你不是按工时计费,你是按月计费。你可能需要在一个下午之内,解决一个类似第五个例子这样的数据库索引问题。请问老板是找一个只会前三个例子的人,还是 5 个例子都会的人?
算法当然重要。虽然在程序中不一定能随时体现,但是是你能力的体现,也是你老板找人的重要标准。985 本硕博连读的你和大专毕业 7 天速成算法的人怎么拉开差距?靠那张文凭,和你的算法实现能力。