Don*_*ino 5 algorithm complexity-theory mergesort divide-and-conquer
我找到了解决此任务的一个问题.
你有N个学生和N个课程.学生只能参加一门课程,许多学生可以参加一门课程.如果他们参加同一课程,两名学生是同学.如何找出N学生中是否有N/2名同学？
条件:你可以带两个学生,问他们是不是同学,只有你可以得到的答案是"是"或"否".你需要在O(N*log(N))中执行此操作.
我只需要知道如何制作它,伪代码就可以了.我想它会将学生列表分成合并排序,这给了我复杂性的对数部分.任何想法都会很棒.
我会发表一些我的想法.. 首先，我认为我们需要做一些像合并排序这样的事情，来制作对数部分...我想，在最低级别，我们只有 2 个学生进行比较，我们只是询问并得到答案。但这并不能解决任何问题。在这种情况下，我们只有 N/2 对学生和知识，他们要么是同学，要么不是同学。这没有帮助..
下一个想法好一点。我没有将该组划分为最低水平，但当我有 4 名学生时我就停止了。所以我有 N/4 个小集合，我将每个人相互进行比较。如果我发现他们中至少有两个是同学，那就太好了。如果不是，而且他们都来自不同的班级，我就完全忘记了那组 4 人。当我将其应用到每个组时，我开始通过比较那些已经被标记为同学的人来将他们加入到 8 人组中。（感谢传递性）。再说一次……如果有至少 4 个同学，8 人一组，我就很高兴，如果没有，我就会忘记那个组。应该重复此操作，直到我有两组学生并对两组学生进行比较以获得最终答案。但问题是，一半可以有 n/2-1 名同学，而另一半只有一名学生与他们匹配……而这个算法不适用于这个想法。