编写线性算法 [英] Writing an linearithmic algorithm

问题描述

这是我的一项任务的问题.

This is a question for one of my assignments.

给出四个由N个名称组成的列表，设计一个线性运算算法来确定是否所有四个列表都具有相同的名称.

Given four lists of N names, devise a linearithmic algorithm to determine if there is any name common to all four lists.

最接近满足O(n log n)的解决方案，仅在只有两个数据集的情况下有效.遍历其中一组并使用二进制搜索找到匹配项.

The closest I've come to a solution that satisfies O(n log n), only works if there are only two data sets. Iterating through one of the sets and using binary search to find a match.

关于如何解决此问题的任何提示?我首先将其发布在programmers.stackexchange上，但是大多数答复都将linearithmic误认为是linearithmic.

Any hints on how to solve this? I first posted this on programmers.stackexchange, but most of the replies mistook linearithmic for linear.

推荐答案

您提出的算法可以扩展为与任意数量(恒定)的列表一起使用:

The algorithm you proposed can be extended to work with any (constant) number of lists:

• 使用O(n * log n)排序对除了一个列表以外的所有列表进行排序.
• 遍历未排序的列表.
• 对于每个项目，对每个排序列表使用二进制搜索以查看它们是否全部存在.

这花费与您的解决方案相同的时间，然后乘以一个常数(列表数).所以它仍然是O(n * log n).

This takes the same amount of time as your solution, multiplied by a constant (the number of lists). So it is still O(n * log n).

请注意，也可以通过使用哈希表而不是sort + Binary搜索来获得O(n)平均情况的运行时.

Note that it is also possible to get an O(n) average-case runtime by using hash tables instead of sort + binary search.

这篇关于编写线性算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！