求助：如何优化C#中具有立方时间复杂度的算法？

这段算法的时间复杂度我认为是立方级的（有人觉得是平方级），我尝试降低复杂度好一阵了，但完全卡壳了。求一些提示或思路就行，不用完整解答。

代码片段 #

var ParentChildList = new List<Dictionary<string, object>>();

foreach (var parent in Parents) 
{
    var dict = new Dictionary<string, object>();
    dict.Add(parent.name, new List<int>() {0});

    foreach (var child in parent.Children) {
        var datesOfBirth = child.Pets.Select(x => x.Pet.DateOfBirth.ToString()).ToList();
        var childIds = child.Pets.Select(x => x.ChildId).ToList();

        dict[child.Name] = new
        {
            dateOfBirth = datesOfBirth,
            childId = childIds
        };
    }

    ParentChildList.Add(dict);
}

注：Parents是List<Parent>类型

优化提示 #

• 先明确复杂度：你的算法本质是三层遍历嵌套（Parent → Child → Pet），如果总Pet数是P，总Child数是C，总Parent数是Pa，复杂度是O(PaC_avgP_per_child)，均匀分布下确实是立方级；但如果把所有Pet的总量算成N，也可以看成O(N)——先理清规模变量定义，再针对性优化。
• 减少重复遍历：当前对每个Child的Pets做了两次Select遍历，完全可以合并成一次遍历，同时收集DateOfBirth.ToString()和ChildId，减少一半的Pet遍历次数。
• 避免不必要的装箱：用Dictionary<string, object>会导致值类型/匿名类型装箱，换成强类型的自定义类或结构体，能减少内存开销和后续性能损耗。
• 提前预处理数据：如果DateOfBirth.ToString()的格式固定，可以提前把所有Pet的日期字符串预生成好，避免遍历过程中重复执行字符串转换操作。

内容的提问来源于stack exchange，提问作者Holmes