时间戳

首页 > 解决方案 > O(n^2) 比 O(n) 快吗？

c# - O(n^2) 比 O(n) 快吗？

问题描述

我写了一个小程序来测试我创建的两个单独的扩展方法的速度，在下面的截图中详细说明：

public static class Extensions
{
    public static List<string> ParseEmails(this string[] emails, char[] charsToSplitOn)
    {
        List<string> list = new List<string>();
        foreach (string email in emails)
        {
            string[] splitArr = email.Replace(" ", "").Split(charsToSplitOn, StringSplitOptions.RemoveEmptyEntries);
            foreach (string item in splitArr)
            {
                list.Add(item);
            }
        }
        return list;
    }

    public static string[] ParseEmails2(this string[] emails, char[] charsToSplitOn)
    {
        string str = string.Empty;
        foreach (string item in emails)
        {
            str += item + ';';
        }
        return str.Replace(" ", "").Split(charsToSplitOn, StringSplitOptions.RemoveEmptyEntries);
    }
}

在此处输入图像描述

Main 方法初始化一个Stopwatch类以跟踪每个方法执行iterations的时间量。

第一种方法在另一个循环中ParseEmails有一个循环，而第二种方法“ParseEmails2”只有一个循环。forforfor

我希望第二种方法 ,ParseEmails2会更快，因为据我了解，这是在 O(n) 时间内完成的，而我的第一种方法 ,ParseEmails是在 O(n^2) 时间内完成的。

如果这是真的，那么我的结果不应该指向ParseEmails2两种方法中的更快吗？

标签： c#.netbig-o

解决方案

您必须准确说明您的意思O(n^2)。是什么n？如果 n 对应于电子邮件的数量（在emails数组中），则第一个方法在 的规模上运行O(n)，因为您对所有电子邮件进行了一次迭代。

在第二种方法中，您使用字符串连接，这意味着您每次循环运行都会创建一个新字符串，从而导致复杂度为O(n^2).

更喜欢StringBuilder在循环中使用或列表而不是连接字符串。

推荐阅读