Как достичь O (n) сложности времени наихудшего случая для этой функции? - PullRequest
Новая
       109

Как достичь O (n) сложности времени наихудшего случая для этой функции?

2 голосов
/ 18 сентября 2019

У меня проблемы с определенной задачей.Это не домашняя работа или что-то еще, это скорее личное дело.И я хочу знать, есть ли хотя бы решение для этого ...

Смысл в том, чтобы достичь ожидаемой O (n) наихудшей временной сложности функции, которая принимает 2 строкимассивы в качестве входных данных (давайте назовем первый A, а второй массив B) и должны возвращать массив целых чисел, где каждый элемент представляет индекс соответствующего элемента в массиве A.

ТакВот как должна выглядеть функция: 

private static int[] GetExistingStrings(string[] A, string[] B) { ... }
  • Массив A содержит все возможные имена
  • Массив B содержит имена, которые следует исключить (т. е. если некоторыеимена, хранящиеся в массиве B, также находятся в массиве A, их индексы не должны включаться в выходной массив int [], также возможно, что этот массив может содержать некоторые случайные строки, которые необязательно могут присутствовать вмассив A ИЛИ он может даже быть пустым.

Например, если у нас есть эти массивы: 

string[] A = { "one", "two", "three", "four" }; // 0, 1, 2, 3
string[] B = { "two", "three" }; // Indices of "two" and "three" not taken into account

Функция должна вернуть: 

int[] result = { 0, 3 }; // Indices of "one" and "four"

Сначала я пытаюсьделаю это очевидным и простым способом (с вложенными циклами for): 

private static int[] GetExistingStrings(string[] A, string[] B)
{
    LinkedList<int> aIndices = new LinkedList<int>();

    for (int n = 0; n < A.Length; n++)
    {
        bool isExcluded = false;
        for (int m = 0; m < B.Length; m++)
        {
            if (A[n].Equals(B[m]))
            {
                isExcluded = true;
                break;
            }
        }

        if (!isExcluded)
        {
            aIndices.AddLast(i);
        }
    }

    int[] resultArray = new int[aIndices.Count];
    aIndices.CopyTo(resultArray, 0);
    return resultArray;
}

Я использовал LinkedList, потому что мы не можем знать, каким должен быть размер массива выходного файла, а также потому, что добавляем новые узлы к этомусписок - это постоянная O (1) операция.Проблема здесь, конечно, состоит в том, что эта функция (как я предполагаю) имеет O (n * M) сложность времени.Итак, нам нужно найти другой способ ...

Мой второй подход был следующим: 

private static int[] GetExistingStrings(string[] A, string[] B)
{
    int n = A.Length;
    int m = B.Length;

    if (m == 0)
    {
        return GetDefaultOutputArray(n);
    }

    HashSet<string> bSet = new HashSet<string>(B);
    LinkedList<int> aIndices = new LinkedList<int>();

    for (int i = 0; i < n; i++)
    {
        if (!bSet.Contains(A[i]))
        {
            aIndices.AddLast(i);
        }
    }

    if (aIndices.Count > 0)
    {
        int[] result = new int[aIndices.Count];
        aIndices.CopyTo(result, 0);
        return result;
    }

    return GetDefaultOutputArray(n);
}

// Just an utility function that returns a default array
// with length "arrayLength", where first element is 0, next one is 1 and so on...
private static int[] GetDefaultOutputArray(int arrayLength)
{
    int[] array = new int[arrayLength];
    for (int i = 0; i < arrayLength; i++)
    {
        array[i] = i;
    }
    return array;
}

Здесь была идея добавить все элементы массива B в HashSet и затем использоватьэто метод Contains() для проверки на равенство в цикле for.Но я не могу точно рассчитать временную сложность этой функции ... Я точно знаю, что код в цикле for будет выполняться n раз.Но что меня больше всего беспокоит, так это инициализация HashSet - следует ли это учитывать здесь?Как это влияет на сложность времени?эта функция O (n) ?Или O (n + m) из-за инициализации HashSet?

Есть ли способ решить эту задачу и добиться O (n) ?

Ответы [ 2 ]

3 голосов
/ 19 сентября 2019

Если у вас есть n элементы в A, m элементы в B, а строки имеют длину k, ожидаемое время подхода хэш-карты составляет O(k*(m + n)).К сожалению, худшее время - O(km(m + n)), если алгоритм хеширования не работает.(Вероятность того, что это очень мало.) Я имел это неправильно раньше, спасибо @PaulHankin за исправление.

Чтобы получить O(k*(m + n)) худшее время, мы должны взять совсем другоеподход.Что вы делаете, это строите три из B. И теперь вы просматриваете каждый элемент A и просматриваете его в три.В отличие от хэша, три гарантирует гарантированную производительность в худшем случае (и, что еще лучше, позволяет выполнять поиск по префиксам, даже если мы этого не используем).Этот подход дает нам не только ожидаемое среднее время O(k*(m + n)), но и то же самое худшее время.

Вы не можете добиться большего успеха, чем это, потому что простая обработка списков требует обработки O(k*(m + n)) данных.

0 голосов
/ 19 сентября 2019

Вот как вы можете переписать свой второй подход, используя LINQ, а также выбрать сравнение строк без учета регистра: 

public static int[] GetExistingStrings(string[] first, string[] second)
{
    var secondSet = new HashSet<string>(second, StringComparer.OrdinalIgnoreCase);
    return first
        .Select((e, i) => (Element : e, Index : i))
        .Where(p => !secondSet.Contains(p.Element))
        .Select(p => p.Index)
        .ToArray();
}

Сложность времени и пространства одинакова (O (n)).Это просто более модный способ сделать то же самое.

...