如果问题空间不够具体,如何评估算法的效率?

你不能,这是无法估量的。

您只能通过定义您将看到的“一般”输入来定义“一般”哪个更好。例如,你可以建立一个输入的概率模型,使得V的期望值是n的函数,然后在这个模型下选择一个期望运行时间最好的。但是在构建模型的过程中可能会有任意的选择,因此不同的模型给出不同的答案。一个模型可能会随机选择坐标,另一个模型可能会查看您正在考虑编写的某个程序的实际用例,并查看它将遇到的输入的分布。

这类似于试图回答“你看到的下一个人的腿数高于(平均)平均数的概率是多少?”。

我们可能会隐含地假设,你遇到的下一个人将随机从人群中均匀分布(因此答案是“略少于一”,因为平均值小于模式平均值,绝大多数人处于模式)。

或者我们可以假设你和另一个人的下一次会面是从两个人之间的所有会面集合中以均匀分布的方式随机选择的,在这种情况下,答案仍然是“略少于一次”,但我认为,与第一个一条腿和零条腿的人不完全一样,他们很可能与“他们自己的同类”聚集在一起,比他们在人群中出现的频率略高。或者可能他们聚集的较少,我真的不知道,我只是不明白,一旦考虑到退伍军人协会等等,为什么会完全一样。

或者我们可以利用关于你的知识——如果你和一只脚的人住在一起,那么答案可能是“非常略高于0”。

三个答案中哪一个是“正确的”完全取决于你禁止我们谈论的上下文。所以我们不能谈论哪个是正确的。

既然你不知道每个药丸都有什么作用,你是吃红色药丸还是蓝色药丸?

如果真的没有足够的信息来决定,就没有足够的信息来决定。任何猜测都一样好。

也许,在某些情况下,有可能获得额外的信息来做决定。我还没有详细研究过您的示例,但匈牙利算法似乎对内存的要求更高。这可能是使用最大流算法的一个原因。

你没有。我想你已经很清楚地说明了这一点。我认为合适的实用解决方案是在不同的线程中派生出两个实现,然后获取首先返回的响应。如果您更聪明,您可以启发式地将请求路由到实现。

许多算法需要超出机器物理最大值的大量内存,在这种情况下,选择了时间效率较低但空间效率较高的算法。

考虑到我们有分布式并行计算,我建议你让两匹马都跑,让结果自己说话。

这是一个有效的问题,但没有“正确”的答案,因为它们是无与伦比的,所以没有“更好”的概念。

如果您的兴趣是实际的,那么您需要分析实践中可能出现的输入类型,以及这两种算法的实际运行时间(包括常量)。

如果你的兴趣是理论上的,最坏情况分析通常是标准的,那么,就输入大小而言,O(V )算法更好:你知道V¤n ² ,但你不能用V来多项式约束n,正如你自己所展示的。当然,理论上最好的算法是一种混合算法,当其中任何一个先完成时运行并停止,因此它的运行时间将是 ^{三 三} )).

按照你的问题的定义,它有两个大小-n和点数,所以这个问题没有答案。