这个问题一直困扰着我的脑海......
假设我有一个项目列表和它们的等价关系,并且比较两个项目需要恒定的时间.我想返回项目的分区,例如链接列表列表,每个列表包含所有等效项目.
这样做的一种方法是将等价扩展到项目的排序并对它们进行排序(使用排序算法); 那么所有等价物品都会相邻.
但它可以比排序更有效地完成吗？这个问题的时间复杂度是否低于排序？如果没有,为什么不呢？
sorting algorithm partitioning time-complexity
algorithm ×1
partitioning ×1
sorting ×1
time-complexity ×1