Pat*_*k M 13 sorting algorithm big-o
我正在寻找一种排序算法,它可以为每个元素1提供最小和最大范围.问题域是一种推荐引擎,它将一组业务规则(限制)与推荐得分(值)相结合.如果我们有推荐(例如特殊产品或交易)或我们想要出现在列表顶部附近的公告(例如"这是非常重要的,请记住验证您的电子邮件地址以参与即将到来的促销活动!")或在列表底部附近(例如"如果您喜欢这些建议,请点击此处获取更多信息......"),他们将在某些位置限制的情况下进行策划.例如,这应该始终位于顶部位置,这些位置应位于前10位或中间5位等.此策展步骤提前完成并在给定时间段内保持固定,并且出于商业原因必须保持非常灵活.
请不要质疑业务目的,UI或输入验证.我只是想在我给出的约束中实现算法.请将此视为学术问题.我将努力提供严格的问题陈述,非常欢迎对问题的所有其他方面的反馈.
因此,如果我们对chars 进行排序,我们的数据将具有结构
struct {
char value;
Integer minPosition;
Integer maxPosition;
}
Where minPosition和maxPosition可能为null(不受限制).如果在所有位置限制为空的算法上调用它,或者所有minPositions都为0或更小并且所有maxPositions都等于或大于列表的大小,则输出将按char升序排列.
该算法只会重新安排两个元素,如果minPosition和maxPosition这两个元素不会被他们的新位置被侵犯.基于插入的算法将项目提升到列表顶部并重新排序其余部分具有明显的问题,即每次迭代后必须重新验证每个后续元素; 在我的脑海中,排除了这些算法具有O(n 3)复杂度,但如果没有考虑相反的证据,我将不排除这些算法.
在输出列表中,当且仅当位置约束集指示它时,某些元素的值才会出现故障.这些输出仍然有效.
例如,以下是输入列表(<char>(<minPosition>:<maxPosition>)其中,Z(1:1)表示Z必须位于列表的前面,并M(-:-)指示M可能位于最终列表中的任何位置和自然顺序(仅按值排序)是A...M...Z)和他们的最佳订单.
Input order
A(1:1) D(-:-) C(-:-) E(-:-) B(-:-)
Optimal order
A B C D E
这是一个简单的例子,表明自然顺序在没有约束的列表中占优势.
Input order
E(1:1) D(2:2) C(3:3) B(4:4) A(5:5)
Optimal order
E D C B A
此示例显示完全约束列表的输出顺序与给定的顺序相同.输入已经是有效且最佳的列表.对于这样的输入,该算法仍应在O(n log n)时间内运行.(我们的初始解决方案能够将任何完全受约束的列表短路以在线性时间内运行;我添加了示例,以便将最佳和有效的定义驱动回家,并且因为我认为一些基于交换的算法将此处理为更糟糕的情况. )
Input order
E(1:1) C(-:-) B(1:5) A(4:4) D(2:3)
Optimal Order
E B D A C
E受约束1:1,因此即使它具有最低值,它也是列表中的第一个.A同样受到限制4:4,所以它也是出于自然秩序.B具有基本相同的约束,C并且可能出现在最终列表中的任何位置,但由于价值B而在之前C.D可能位于第2或第3位,因此B由于其自然顺序而在之后C因为其约束而出现.
需要注意的是订单的最终不顾自然秩序是完全不同的是正确的(这仍然是A,B,C,D,E).如前一段所述,此列表中的任何内容都不能在不违反一个或多个项目约束的情况下重新排序.
Input order
B(-:-) C(2:2) A(-:-) A(-:-)
Optimal order
A(-:-) C(2:2) A(-:-) B(-:-)
C仍然不为所动,因为它已经处于唯一有效的位置.B被重新排序到最后因为它的价值低于两者A的价值.实际上,将会有其他字段来区分两者A,但从算法的角度来看,它们是相同的并且保留OR反转它们的输入顺序是最佳解决方案.
Input order
A(1:1) B(1:1) C(3:4) D(3:4) E(3:4)
Undefined output
该输入是有两个原因无效:1)A和B均约束到位置1和2) C,D和E被约束的范围不是仅可容纳2个元素.换言之,范围1:1和3:4是过度约束.但是,约束的一致性和合法性是通过UI验证来强制执行的,因此如果它们不正确,它正式不是算法问题,并且算法可以在这种情况下返回尽力排序或原始排序.将这样的输入传递给算法可以被认为是未定义的行为 ; 什么都可能发生.所以,对于其他问题......
我们目前已经确定了一个定制的选择排序(运行时复杂度为O(n 2))并且合理地证明它适用于位置限制有效且一致的所有输入(例如,对于给定位置或位置范围不超额预订) .
是否有一种排序算法可以保证返回最优的最终订单并且运行时间优于O(n 2)时间复杂度？3
我觉得可以通过提供一个接受每个元素的候选目标位置的自定义比较器来修改库标准排序算法来处理这些约束.这相当于每个元素的当前位置,因此可能修改值保持类以包含元素的当前位置,并在compare(.equals())和swap方法中进行额外记帐就足够了.
但是,我想的越多,在O(n log n)时间内运行的算法就无法正常使用这些限制.直观地说,这样的算法是基于运行ñ比较日志N倍.在为log N是通过利用一个分而治之机构,其仅适用于特定位置的特定候选者进行比较来实现的.
换句话说,对于任何O(n log n)排序算法存在具有有效位置约束的输入列表(即反例),其中候选元素将与元素(或在Quicksort和变体的情况下的范围)与/与之比较.它无法交换,因此永远不会移动到正确的最终位置.如果这太模糊了,我可以为mergesort和quicksort提出一个反例.
相反,O(n 2)排序算法进行详尽的比较,并且总是可以将元素移动到其正确的最终位置.
问一个实际问题:当我推断O(n log n)排序不能保证找到有效订单时,我的直觉是否正确？如果是这样,你能提供更具体的证据吗？如果没有,为什么不呢？关于这类问题还有其他现有的研究吗？
1:我无法找到一组搜索术语,指出我对这种排序算法或约束的任何具体分类的方向; 这就是为什么我要问一些关于复杂性的基本问题.如果存在此类问题的术语,请将其发布.
2:验证是一个单独的问题,值得自己研究和算法.我很确定有效订单的存在可以在线性时间内证明:
编辑:此验证算法本身实际上是O(n 2).最坏的情况下,每一个元素都有约束1:n,你最终会走你的列表ñ元组ñ倍.这仍然与问题的范围无关,因为在实际问题域中,约束被强制执行一次而不会改变.
确定给定列表的有效顺序更加容易.只需根据约束检查每个元素的当前位置.
3:诚然,这有点过早优化.我们最初的用途是针对相当小的列表,但我们正在考虑扩展到更长的列表,所以如果我们现在可以进行优化,我们现在可以获得小的性能提升,并且稍后会有大的性能提升.此外,我的好奇心被激发了,如果有关于这个主题的研究,我希望看到它并(希望)从中学习.
不见得*。我假设你的意思是 O(n log n) 就地、不稳定、离线的平均运行时间。大多数改进冒泡排序平均运行时间为 O(n^2) 的排序算法（例如tim sort）都依赖于这样的假设：比较子集中的 2 个元素将在超集中产生相同的结果。快速排序的较慢变体将是解决范围限制的好方法。最坏的情况不会改变，但平均情况可能会减少，并且算法将具有现有有效排序的额外约束。
是... O(n log n) 排序不能保证找到有效的顺序吗？
我所知道的所有流行排序算法只要满足约束条件就保证找到顺序。形式分析（具体证明）位于每种算法的维基百科页面上。
对于此类问题还有其他现有研究吗？
是的; 像IJCSEA这样的期刊有很多有排序研究。
*但这取决于您的平均数据集。