部分排序,严格弱排序,总排序,应用程序的主要区别是什么



[SGI官方文件]

由于不可反身性和传递性,运算符

我还阅读了文档中严格弱排序的定义:严格弱排序

前三个公理,不可反身性、反对称性和传递性, 是部分排序的定义;等价的传递性 是严格弱排序的定义所要求的。总计 排序是满足更强大条件的排序:等价 必须与平等相同。

我不太确定这些定义。一些主要问题:

偏排序隐式定义等价 1.Is?

2.严格弱排序总排序呢?

3.STL在排序算法中要求严格的弱排序,为什么不是部分排序或总排序?对于这个问题,我读过一些教科书,通过证明规则满足三个公理来证明比较规则是有效的:不可反性、反对称性、传递性(这是偏序的定义),文档引用该运算符<总是满足这个定义,那么为什么我们不能只使用部分排序来比较对象,或者等效地使用运算符>

部分排序本质上是<= 。如果两者都a <= bb <= a那么你可以说a等同于b。但也有可能既不a <= b也不b <= a——这两个元素是无可比拟的。因此,您不能对具有偏序关系的集合强加总序(就像std::sort需要的那样)——充其量您可以进行拓扑排序。你也不能推导出等价关系——同样,可能存在无法比拟的元素。

严格的弱排序就像<.它不允许同时使用a < bb < a,如果既不a < b也不b < a,你可以只发音ab等价。

总排序只是严格的弱排序,其中两个元素是等价的,当且仅当它们相等时(这只有在除了小于谓词之外还有一个相等比较谓词时才有意义,并且没有C++标准库算法同时使用两者,因此这个问题在这种情况下基本上没有意义)。

相关内容

  • 没有找到相关文章

最新更新