c# – 高级：如何优化我的复杂O(n2)算法

个人实体有

> IList< DateRangePlaces>每个都有

> IList< Place>可能的地方

>将日期模式安排为ie. 10天可用4不可用

在特定的DateRangePlaces日期范围内,人们必须遵守计划模式,无论人们是否可以去特定的地方.

>地方实体有

> IList< DateRangeTiming>每个定义每个日期范围内的开/关时间

重叠日期范围适用于LIFO.所以对于以前已经定义的每一天,新的时序定义都是偏好的.

问题

现在我需要这样做(伪代码)：

for each Place
{
    for each Day between minimum and maximum date in IList<DateRangeTiming>
    {
        get a set of People applicable for Place and on Day
    }
}

这意味着执行我的任务的步骤大约为：

∑_(places)( ∑_(days) × ∑_(people) )

这对我的理解是

O(x × y_x × z)

并且可能近似于该算法的复杂性：

O(n³)

我不是理论上的专家,所以你可以自由地修正我的假设.真正的是,这种复杂性是绝对不可接受的,特别是考虑到我将在很多地方和人们的长时间范围内运作.

从公式近似我们可以看到,人们将被重复迭代很多次.因此,我至少要优化这部分.为了缓解事情,我改变了一点

Person.IList<DateRangePlaces>.IList<Place>

至

Person.IList<DateRangePlaces>.IDictionary<int,Place>

这将给我一个更快的结果,无论一个人可以去某个地方在特定的日期,因为我只会检查是否Place.Id存在于字典中,而IList.Where()LINQ子句将不得不扫描整个列表每个和每一次.

题

>你能否提出我可以在我的算法中实现的任何其他优化,使其更快,甚至使它在较大的O符号方面变得不那么复杂？
>您将使用哪些内存结构类型,以及为什么(列表,字典,堆栈,队列…)可以提高性能？

附录：整个问题更复杂

还有其他的复杂性,我没有提到,因为我想简化我的问题,使其更加清楚.所以.还有：

Place.IList<Permission>
Person.IList<DateRangePermission>

所以这些地方需要特殊的权限,而且人们有限的时间可以到期许可.

除此之外,还有

Person.IList<DateRangeTimingRestriction>

这只告诉特定的时间,人们可以在特定的日期范围内去某个地方.和

Person.IList<DateRangePlacePriorities>

其定义特定日期范围的地点优先级.

在获得适用人员的这个过程中,我还必须计算每个人每个与

一个人可以在特定的一天访问的地方的数量
>那个人的地点优先考虑因素

所有这些都是为什么我决定在内存中操作这些数据,而不是使用非常复杂的存储过程,也可以进行多个表扫描以获取每个人和地点和日子的因素.

我认为这样的存储过程将是复杂的处理和维护的方式.所以我宁愿先获取所有的数据(放置适当的内存结构来帮助性能),然后在内存中处理它.