如何使用嵌套循环降低 C# 方法的时间复杂度

Question

我正在使用 Kubernetes C# 客户端通过更改具有特定图像名称的容器中的图像标签来修补集群中的部署。

据我所知，该方法的第一个版本似乎效率不高，它的时间复杂度为 O(n2)。

private List<V1Deployment> UpdateImageTag(string imageName, string tag, List<V1Deployment> deployments)
        {
            var updatedDeployments = new List<V1Deployment>();

            if (deployments?.Count > 0)
            {
                foreach (var deployment in deployments)
                {
                    foreach (var container in deployment?.Spec?.Template?.Spec?.Containers.SkipWhile(x => !x.Image.ToLowerInvariant()
                                                                                                            .StartsWith(imageName.ToLowerInvariant())))
                    {
                        if (container is null)
                        {
                            // Log it and go to the next container.
                            _logger.LogDebug("Deployment {Deployment} has a null container, skipping it.", deployment?.Metadata?.Name);
                            continue;
                        }
                        SetImageTag(tag, container);

                        if (!updatedDeployments.Contains(deployment))
                        {
                            updatedDeployments.Add(deployment);
                        }
                    }
                }
            }

            return updatedDeployments;
        }

如何以更有效的方式实现这一点？

Answer 1

与评论相反，worst-case 时间复杂度实际上是 O(n^2)，其中 n 是 deployment 的长度。但不是因为嵌套foreach;这是因为调用 Contains。实际上它比那更糟糕 - 复杂度更准确地说是 O(m*n^2)，其中 m 是每次部署的容器数量，因为 Contains 位于内部循环中。

这样做怎么样（复杂度 O(m*n)，给定输入数据结构是最优的）：

    private List<V1Deployment> UpdateImageTag(string imageName, string tag, List<V1Deployment> deployments)
    {
        if (deployments == null)
        {
            return new List<V1Deployment>();
        }

        var imageNameLower = imageName.ToLowerInvariant();

        var matches = deployments
            .Select(deployment => KeyValuePair.Create(
                deployment, 
                deployment.Spec?.Template?.Spec?.Containers
                    .Where(c => !c.Image.ToLowerInvariant().StartsWith(imageNameLower))))
            .Where(kvp => kvp.Value != null)
            .ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
            

        foreach (var container in matches.Values.SelectMany(x => x))
        {
            SetImageTag(tag, container);
        }

        return matches.Keys.ToList();
    }

如何使用嵌套循环降低 C# 方法的时间复杂度

How to reduce time complexity of a C# method with nested loops

c#

big-o