时间戳

首页 > 解决方案 > 如何使用嵌套循环降低 C# 方法的时间复杂度

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

问题描述

我正在使用 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;
        }

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

标签： c#big-o

解决方案

与评论相反，最坏情况下的时间复杂度实际上是的长度O(n^2)在哪里。但这不是因为嵌套; 这是因为调用. 实际上它比这更糟糕 - 更准确地说，复杂性是每个部署的容器数量，因为它位于内部循环中。ndeploymentforeachContainsO(m*n^2)mContains

这样做怎么样（复杂性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();
    }

推荐阅读