最近有一篇帖子提出了以下问题:
你有一个(X,Y)坐标的二维平面.选择一堆随机点.您需要选择最大可能的选定点集,这样没有两个点共享一个X坐标,没有两个点共享一个Y坐标.
这是提供的所有信息.
提出了两种可能的解决方案.
一个建议使用最大流算法,使得每个选定的点映射到链接的路径(源 → X → Y → 下沉).这在O(V 3)时间内运行,其中V是所选顶点的数量.
另一个(我的)建议使用匈牙利算法.创建1x的n×n矩阵,然后将每个选择的(x,y)坐标设置为0.匈牙利算法将为您提供此矩阵的最低成本,答案是所选的坐标数等于0.此运行在O(n 3)时间内,其中n是行数或列数中的较大者.
我的理由是,对绝大多数情况来说,匈牙利算法会更快; 在每行或每列有一个选定点的情况下,V等于n,对于任何超过该值的情况,V等于n:给定50×50矩阵,选择坐标的一半,V为1,250,n为50 .
反驳的是有些情况,例如10 9 ×10 9矩阵,只选择了两个点,其中V是2,n是1,000,000,000.对于这种情况,匈牙利算法运行时间过长,而最大流量算法快速致盲.
问题是:鉴于问题没有提供有关矩阵大小或选择给定点的概率的任何信息(因此您无法确切知道),您通常如何确定哪种算法？问题是更好的选择吗？
不能，这是不可估量的。
您只能通过定义“一般”将看到的输入来定义“一般”更好。例如，您可以建立一个输入的概率模型，以便 V 的预期值是 n 的函数，并选择在该模型下具有最佳预期运行时间的模型。但在构建模型时可能会做出任意选择，因此不同的模型会给出不同的答案。一个模型可能会随机选择坐标，另一种模型可能会查看您正在考虑编写的某些程序的实际用例，并查看它将遇到的输入的分布。
您也可以讨论哪个具有最好的最坏情况（在给定约束的所有可能输入中），其优点是易于定义，但缺点是不能保证告诉您有关实际程序性能的任何信息。例如，在最坏的情况下，HeapSort 比 QuickSort 更快，但在平均情况下更慢。哪个更快？取决于你关心的是平均情况还是最坏情况。如果你不关心哪种情况，你就不能关心哪个“更快”。
这类似于试图回答“你看到的下一个人的腿数高于（平均）平均数的概率是多少？”的问题。
我们可能隐含地假设你遇到的下一个人将从人群中均匀分布地随机选择（因此答案是“略小于一”，因为平均值小于众数平均值，并且绝大多数人们处于该模式）。
或者我们可能会假设您与另一个人的下一次会议是从两个人之间的所有会议集合中均匀分布地随机选择的，在这种情况下答案仍然是“略小于一个”，但我认为与以下值不完全相同第一个——单腿和零腿的人很可能与“他们自己的同类”聚集在一起，其频率比他们在人口中所暗示的频率要高得多。或者可能他们聚集得更少，我真的不知道，我只是不明白为什么一旦考虑到退伍军人协会等因素，情况应该完全相同。
或者我们可能会使用有关您的知识 - 如果您与单腿的人住在一起，那么答案可能是“略高于 0”。
这三个答案中哪一个是“正确的”恰恰取决于您禁止我们谈论的上下文。所以我们无法讨论哪个是正确的。