O (n ^ 2) быстрее, чем O (n)?

Question

Я написал небольшую программу для проверки скорости двух отдельных методов расширения, которые я создал, подробно показано на скриншоте ниже:

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, имеет цикл for внутри другого цикла forв то время как второй метод 'ParseEmails2' имеет только один цикл for.

Я бы ожидал, что тогда второй метод, ParseEmails2, будет быстрее, поскольку, насколько я понимаю, это делается в O(n) время, тогда как мой первый метод, ParseEmails, выполняется за время O (n ^ 2).

Если это так, то мои результаты не должны указывать на то, что ParseEmails2 быстрееиз двух методов?

Answer 1

Ну ... вы, похоже, не понимаете цели обозначения O, O меньше о производительности и больше о постоянстве производительности.O(n²) означает параболу и O(n) прямую линию, но она не говорит вам о реальном времени.Поэтому, если у вас есть много элементов, алгоритм O(n) должен быть быстрее.Причиной этого может быть то, что вы используете string += и + операторы, которые используют copy on write -семантику C # string.

Answer 2

Вы должны быть точными в том, что вы подразумеваете под O(n^2). Что такое n? Если n соответствует количеству писем (в массиве emails), то первый метод выполняется в масштабе O(n), потому что вы перебираете все письма один раз.

Во втором методе вы используете конкатенацию строк, что означает, что вы создаете новую строку при каждом запуске цикла, что приводит к сложности O(n^2).

Предпочитают использовать StringBuilder или Списки над объединяющими строками внутри цикла.

Answer 3

Вы должны проверить эту ссылку. конкатенация строк и производительность компоновщика Конкатенация строк и Строитель строк. Производительность

Строитель строк, скорее всего, будет немного быстрее в этом случае, но на самом деле этого, вероятно, будет недостаточно, чтобы беспокоиться. Сколько раз вы воссоздаете строку (потому что строки являются неизменяемыми и объединение заставляет создавать новую строку из двух существующих).

Из-за выделения памяти на самом шаге потребуется больше времени.

Answer 4

ParseEmails2 на самом деле не O (n), потому что

str += item + ';';

содержит цикл.