hadoop不会改变任何事物的渐进复杂性。它只是关于减少大o忽略的常数因子。
把分布式计算的结果放在一起总有一些开销。然而，在您的三个问题的情况下，使用组合器将减少最终排序为o（1）。我不知道当只有一个键时，在每个map主机上为组合器分组的本地排序有多复杂。在那种情况下，它可能比o（n lgn）好。

我还没有在实践中尝试过这种方法，但是我相信通过为您的工作定义一个自定义排序和分组比较器，您可以有效地禁用排序。您需要使用排序比较器，它表示所有键在排序时都是相等的。我相信这将使所有的种类至少尽可能少的工作-一通。但是您希望保留默认的分区器和分组比较器，因此工作仍然以相同的方式分布，并且相同的值与相同的键一起使用。
我不知道这是否是o（n），因为内部还有很多其他事情，比如合并。
而且，big-o是一个非常粗糙的速度度量。像高效的可写文件和组合器之类的东西将比这些问题有更大的区别。
当然，我可能不会建议您为此类工作构建自定义mapreduce作业。这是hive可以为您解答的问题，尽管它只是将任务委派给mapreduce作业，并且比您最初设想的简单mapreduce要慢。
像impala这样的实时工具可以更快地回答这些类型的查询。它们不使用mapreduce，但在hadoop上运行。如果你真的想这么做，我强烈建议你朝那个方向看。