MEX (Minimum EXcluded) Алгоритм поиска минимального отсутствующего числа -3


AliExpress RU&CIS

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


Мы разберем три алгоритма и посмотрим на их производительность.

Добро пожаловать под cut

Предисловие


Перед тем как начать, хотелось бы рассказать — почему я вообще за этот алгоритм взялся?
Всё началось с задачки на OZON.


Как видно из задачи, в математике результатом работы функции MEX на множестве чисел является наименьшим значением из всего набора, который не принадлежит этому множеству. То есть это минимальное значение набора дополнений. Название «MEX» является сокращением для «Minimum EXcluded» значение.


И покопавшись в сети, оказалось, что нет общепринятого алгоритма нахождения MEX…

Есть решения в лоб, есть варианты с дополнительными массивами, графами, но, как-то всё это раскидано по разным углам интернета и нет единой нормальной статьи по этому поводу. Вот и родилась идея — написать эту статью. В этой статье мы разберем три алгоритма нахождения MEX и посмотрим, что у нас получиться по скорости и по памяти.

Код будет на языке C#, но в целом там не будет специфичных конструкций.

Базовый код для проверок будет таким.

static void Main(string[] args)
        {
            //MEX = 2
            int[] values = new[] { 0, 12, 4, 7, 1 };
            
            //MEX = 5
            //int[] values = new[] { 0, 1, 2, 3, 4 };
            
            //MEX = 24
            //int[] values = new[] { 11, 10, 9, 8, 15, 14, 13, 12, 3, 2, 0, 7, 6, 5, 27, 26, 25, 4, 31, 30, 28, 19, 18, 17, 16, 23, 22, 21, 20, 43, 1, 40, 47, 46, 45, 44, 35, 33, 32, 39, 38, 37, 36, 58, 57, 56, 63, 62, 60, 51, 49, 48, 55, 53, 52, 75, 73, 72, 79, 77, 67, 66, 65, 71, 70, 68, 90, 89, 88, 95, 94, 93, 92, 83, 82, 81, 80, 87, 86, 84, 107, 106, 104 };
            
            //MEX = 1000
            //int[] values = new int[1000];
            //for (int i = 0; i < values.Length; i++) values[i] = i;
            
            //Импровизированный счетчик итераций
            int total = 0;
            int mex = GetMEX(values, ref total);
            Console.WriteLine($"mex: {mex}, total: {total}");
            Console.ReadKey();
        }

И еще один момент в статье я часто упоминаю слово «массив», хотя более правильным будет «множество», то заранее хочу извиниться перед теми, кому будет резать слух данное допущение.

Примечание 1 на основе комментариев: Многие придрались к O(n), мол все алгоритмы O(n) и по фигу, что «O» везде разное и не даёт фактически сравнить количество итераций. То для душевного спокойствия поменяем O на T. Где T более-менее понятная операция: проверка или присвоение. Так, как я понимаю, всем будет проще

Примечание 2 на основе комментариев: мы рассматриваем случай когда исходное множество НЕупорядоченное. Ибо сортировка это множества — тоже требует времени.

1) Решение в лоб


Как нам найти «минимальное отсутствующие число»? Самый простой вариант – сделать счетчик и перебирать массив до тех пор, пока не найдем число равное счетчику.

  static int GetMEX(int[] values, ref int total)
        {
            for (int mex = 0; mex < values.Length; mex++)
            {
                bool notFound = true;
                for (int i = 0; i < values.Length; i++)
                {
                    total++;
                    if (values[i] == mex)
                    {
                        notFound = false;
                        break;
                    }
                }
                if (notFound)
                {
                    return mex;
                }
            }
            return values.Length;
        }
    }

Максимально базовый случай. Сложность алгоритма составляет T(n*cell(n/2))… Т.к. для случая { 0, 1, 2, 3, 4 } нам нужно будет перебрать все числа т.к. совершить 15 операций. А для полностью заполного ряда из 100 числе 5050 операций… Так себе быстродейственность.

2) Просеивание


Второй по сложности вариант в реализации укладывается в T(n)… Ну или почти T(n), математики хитрят и не учитывают подготовку данных… Ибо, как минимум, — нам нужно знать максимальное число во множестве.

С точки зрения математики выглядит так.

Берется битовый массив S длинной m (где m – длина массива V) заполненный 0. И в один проход исходному множеству (V) в массиве (S) ставятся 1. После этого в один проход находим первое пустое значение. Все значения больше m можно просто игнорировать т.к. если в массиве «не хватает» значений до m, то явно будет меньше длины m.

static int GetMEX(int[] values, ref int total)
        {
            bool[] sieve = new bool[values.Length];
            for (int i = 0; i < values.Length; i++)
            {
                total++;
                var intdex = values[i];
                if (intdex < values.Length)
                {
                    sieve[intdex] = true;
                }
            }
            for (int i = 0; i < sieve.Length; i++)
            {
                total++;
                if (!sieve[i])
                {
                    return i;
                }
            }
            return values.Length;
        }

Т.к. «математики» – хитрые люди. То они говорят, что алгоритм T(n) ведь проход по исходному массиву всего один…

Вот сидят и радуются, что такой крутой алгоритм придумали, но правда такова.
Первое — нужно пройтись по исходному массиву и отметить это значение в массиве S T1(n)
Второе — нужно пройтись по массиву S и найти там первую попавшеюся свободную ячейку T2(n)
Итого, т.к. все операции в целом не сложные можно упростить все расчеты до T(n*2)

Но это явно лучше решения в лоб… Давайте проверим на наших тестовых данных:

  1. Для случая { 0, 12, 4, 7, 1 }: В лоб: 11 итераций, просеивание: 8 итераций
  2. Для случая { 0, 1, 2, 3, 4 }: В лоб: 15 итераций, просеивание: 10 итераций
  3. Для случая { 11,…}: В лоб: 441 итерация, просеивание: 108 итерация
  4. Для случая { 0,…,999}: В лоб: 500500 итераций, просеивание: 2000 итераций

Дело в том, что если «отсутствующее значение» является небольшим числом, то в таком случае — решение в лоб оказывается быстрее, т.к. не требует тройного прохода по массиву. Но в целом, на больших размерностях явно проигрывает просеиванию, что собственно неудивительно.
С точки зрения «математика» – алгоритм готов, и он великолепен, но вот с точки зрения «программиста» – он ужасен из-за объема оперативной памяти, израсходованной впустую, да и финальный проход для поиска первого пустого значения явно хочется ускорить.

Давайте сделаем это, и оптимизируем код.

static int GetMEX(int[] values, ref int total)
        {
            var max = values.Length;
            var size = sizeof(ulong) * 8;
            ulong[] sieve = new ulong[(max / size) + 1];
            ulong one = 1;
            for (int i = 0; i < values.Length; i++)
            {
                total++;
                var intdex = values[i];
                if (intdex < values.Length)
                {
                    sieve[values[i] / size] |= (one << (values[i] % size));
                }
            }

            var maxInblock = ulong.MaxValue;
            for (int i = 0; i < sieve.Length; i++)
            {
                total++;
                if (sieve[i] != maxInblock)
                {
                    total--;
                    for (int j = 0; j < size; j++)
                    {
                        total++;
                        if ((sieve[i] & (one << j)) == 0)
                        {
                            return i * size + j;
                        }
                    }
                }
            }
            return values.Length;
        }

Что мы тут сделали. Во-первых, в 64 раза уменьшили количество оперативной памяти, которая необходима.

var size = sizeof(ulong) * 8;
ulong[] sieve = new ulong[(max / size) + 1];
Во-вторых, оптимизировали финальную проверку: мы проверяем сразу блок на вхождение первых 64 значений: if (sieve[i] != maxInblock) и как только убедились в том, что значение блока не равно бинарным 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111, только тогда ищем уже вхождение на уровне блока: ((sieve[i] & (one << j)) == 0

В итоге алгоритм просеивание нам дает следующие результат:

  1. Для случая { 0, 12, 4, 7, 1 }: просеивание: 8 итераций, просеивание с оптимизацией: 8 итераций
  2. Для случая { 0, 1, 2, 3, 4 }: просеивание: 10 итераций, просеивание с оптимизацией: 11 итераций
  3. Для случая { 11,…}: просеивание: 108 итерация, просеивание с оптимизацией: 108 итерации
  4. Для случая { 0,…,999}: просеивание: 2000 итераций, просеивание с оптимизацией: 1056 итераций

Так, что в итоге в теории по скорости?

T(n*3) мы превратили в T(n*2) + T(n / 64) в целом, чуть увеличили скорость, да еще объём оперативной памяти уменьшили аж в 64 раза. Что хорошо)

3) Сортировка


Как не сложно догадаться, самый простой способ найти отсутствующий элемент во множестве – это иметь отсортированное множество.

Самый быстрый алгоритм сортировки — это «quicksort» (быстрая сортировка), которая имеет сложность в T1(n log(n)). И итого мы получим теоретическую сложность для поиска MEX в T1(n log(n)) + T2(n)

static int GetMEX(int[] values, ref int total)
        {
            total = values.Length * (int)Math.Log(values.Length);
            values = values.OrderBy(x => x).ToArray();
            for (int i = 0; i < values.Length - 1; i++)
            {
                total++;
                if (values[i] + 1 != values[i + 1])
                {
                    return values[i] + 1;
                }
            }
            return values.Length;
        }

Шикарно. Ничего лишнего.

Проверим количество итераций

  1. Для случая { 0, 12, 4, 7, 1 }: просеивание с оптимизацией: 8, сортировка: ~7 итераций
  2. Для случая { 0, 1, 2, 3, 4 }: просеивание с оптимизацией: 11 итераций, сортировка: ~9 итераций
  3. Для случая { 11,…}: просеивание с оптимизацией: 108 итерации, сортировка: ~356 итераций
  4. Для случая { 0,…,999}: просеивание с оптимизацией: 1056 итераций, сортировка: ~6999 итераций

Здесь указаны средние значения, и они не совсем справедливы. Но в целом: сортировка — не требует дополнительной памяти и явно позволяет упростить последний шаг в переборе.
Примечание: values.OrderBy(x => x).ToArray() – да я знаю, что тут выделилась память, но если делать по уму, то можно изменить массив, а не копировать его…


Вот у меня и возникла идея оптимизировать quicksort для поиска MEX. Данный вариант алгоритма я не находил в интернете, ни с точки зрения математики, и уж тем более с точки зрения программирования. То код будем писать с 0 по дороге придумывая как он будет выглядеть :D

Но, для начала, давайте вспомним как вообще работает quicksort. Я бы ссылку дал, но нормальное пояснение quicksort на пальцах фактически нет, создается ощущение, что авторы пособий сами разбираются в алгоритме пока его рассказывают про него…

Так вот, что такое quicksort:
У нас есть неупорядоченный массив { 0, 12, 4, 7, 1 }
Нам потребуется «случайное число», но лучше взять любое из массива, — это называется опорное число (T).

И два указателя: L1 – смотрит на первый элемент массива, L2 смотрит на последний элемент массива.

0, 12, 4, 7, 1
L1 = 0, L2 = 1, T = 1 (T взял тупа последние)

Первый этап итерации:
Пока работам только с указателем L1
Сдвигаем его по массиву вправо пока не найдем число больше чем наше опорное.
В нашем случае L1 равен 8

Второй этап итерации:
Теперь сдвигаем указатель L2
Сдвигаем его по массиву влево пока не найдем число меньше либо равное чем наше опорное.
В данном случае L2 равен 1. Т.к. я взял опорное число равным крайнему элементу массива, а туда же смотрел L2.

Третей этап итерации:
Меняем числа в указателях L1 и L2 местами, указатели не двигаем.
И переходим к первому этапу итерации.
Эти этапы мы повторяем до тех пор, пока указатели L1 и L2 не будет равны, не значения по ним, а именно указатели. Т.е. они должны указывать на один элемент.

После того как указатели сойдутся на каком-то элементе, обе части массива будут всё еще не отсортированы, но уже точно, с одной стороны «обединённых указателей (L1 и L2)» будут элементы, которые меньше T, а со второй больше T. Именно этот факт нам и позволяет разбить массив на две независимые группы, которые можно сортировать в разных потоках в дальнейших итерациях.

Статья на wiki, если и у меня непонятно написанно

Напишем Quicksort

static void Quicksort(int[] values, int l1, int l2, int t, ref int total)
        {
            var index = QuicksortSub(values, l1, l2, t, ref total);
            if (l1 < index)
            {
                Quicksort(values, l1, index - 1, values[index - 1], ref total);
            }
            if (index < l2)
            {
                Quicksort(values, index, l2, values[l2], ref total);
            }
        }

        static int QuicksortSub(int[] values, int l1, int l2, int t, ref int total)
        {
            for (; l1 < l2; l1++)
            {
                total++;
                if (t < values[l1])
                {
                    total--;
                    for (; l1 <= l2; l2--)
                    {
                        total++;
                        if (l1 == l2)
                        {
                            return l2;
                        }
                        if (values[l2] <= t)
                        {
                            values[l1] = values[l1] ^ values[l2];
                            values[l2] = values[l1] ^ values[l2];
                            values[l1] = values[l1] ^ values[l2];
                            break;
                        }
                    }
                }
            }
            return l2;
        }

Проверим реальное количество итераций:

  1. Для случая { 0, 12, 4, 7, 1 }: просеивание с оптимизацией: 8, сортировка: 11 итераций
  2. Для случая { 0, 1, 2, 3, 4 }: просеивание с оптимизацией: 11 итераций, сортировка: 14 итераций
  3. Для случая { 11,…}: просеивание с оптимизацией: 108 итерации, сортировка: 1520 итераций
  4. Для случая { 0,…,999}: просеивание с оптимизацией: 1056 итераций, сортировка: 500499 итераций

Попробуем поразмышлять вот над чем. В массиве { 0, 4, 1, 2, 3 } нет недостающих элементов, а его длина равна 5. Т.е. получается, массив в котором нет отсутствующих элементов равен длине массива — 1. Т.е. m = { 0, 4, 1, 2, 3 }, Length(m) == Max(m) + 1. И самое главное в этом моменте, что это условие справедливо, если значения в массиве переставлены местами. И важно то, что это условие можно распространить на части массива. А именно вот так:
{ 0, 4, 1, 2, 3, 12, 10, 11, 14 } зная, что в левой части массива все числа меньше некого опорного числа, например 5, а в правой всё что больше, то нет смысла искать минимальное число слева.

Т.е. если мы точно знаем, что в одной из частей нет элементов больше определённого значения, то само это отсутствующие число нужно искать во второй части массива. В целом так работает алгоритм бинарного поиска.

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

В итоге получаем код

static int GetMEX(int[] values, ref int total)
        {
            return QuicksortMEX(values, 0, values.Length - 1, values[values.Length - 1], ref total);
        }

        static int QuicksortMEX(int[] values, int l1, int l2, int t, ref int total)
        {
            if (l1 == l2)
            {
                return l1;
            }
            int max = -1;
            var index = QuicksortMEXSub(values, l1, l2, t, ref max, ref total);
            if (index < max + 1)
            {
                return QuicksortMEX(values, l1, index - 1, values[index - 1], ref total);
            }
            if (index == values.Length - 1)
            {
                return index + 1;
            }
            return QuicksortMEX(values, index, l2, values[l2], ref total);
        }

        static int QuicksortMEXSub(int[] values, int l1, int l2, int t, ref int max, ref int total)
        {
            for (; l1 < l2; l1++)
            {
                total++;
                if (values[l1] < t && max < values[l1])
                {
                    max = values[l1];
                }
                if (t < values[l1])
                {
                    total--;
                    for (; l1 <= l2; l2--)
                    {
                        total++;
                        if (values[l2] == t && max < values[l2])
                        {
                            max = values[l2];
                        }
                        if (l1 == l2)
                        {
                            return l2;
                        }
                        if (values[l2] <= t)
                        {
                            values[l1] = values[l1] ^ values[l2];
                            values[l2] = values[l1] ^ values[l2];
                            values[l1] = values[l1] ^ values[l2];
                            break;
                        }
                    }
                }
            }
            return l2;
        }

Проверим количество итераций

  1. Для случая { 0, 12, 4, 7, 1 }: просеивание с оптимизацией: 8, сортировка MEX: 8 итераций
  2. Для случая { 0, 1, 2, 3, 4 }: просеивание с оптимизацией: 11 итераций, сортировка MEX: 4 итераций
  3. Для случая { 11,…}: просеивание с оптимизацией: 108 итерации, сортировка MEX: 1353 итераций
  4. Для случая { 0,…,999}: просеивание с оптимизацией: 1056 итераций, сортировка MEX: 999 итераций

Итого


Мы получили разные варианты поиска MEX. Какой из них лучше — решать вам.

В целом. Мне больше всех нравится просеивание, и вот по каким причинам:
У него очень предсказуемое время выполнения. Более того, этот алгоритм можно легко использовать в многопоточном режиме. Т.е. разделить массив на части и каждую часть пробегать в отдельном потоке:

for (int i = minIndexThread; i < maxIndexThread; i++)
sieve[values[i] / size] |= (one << (values[i] % size));

Единственное, нужен lock при записи sieve[values[i] / size]. И еще — алгоритм идеален при выгрузке данных из базы данных. Можно грузить пачками по 1000 штук например, в каждом потоке и всё равно он будет работать.

Но если у нас строгая нехватка памяти, то сортировка MEX – явно выглядит лучше.

P.S.


Я начал рассказ с конкурса на OZON в котором я пробовал участвовать, сделав «предварительный вариант» алгоритма просеиванья, приз за него я так и не получил, OZON счел его неудовлетворительным… По каким именно причинам — он так и не сознался… Да и кода победителя я тоже не видел. Может у кого-то есть идеи как можно решить задачу поиска MEX лучше?




Комментарии (100):

  1. GospodinKolhoznik
    /#23145506 / +1

    Эта задача имеет решение за линейное время. Более того, эта задача имеет красивое решение за линейное время в чисто функциональном стиле, без использования массивов и мутабельных переменных.

    • RussianDragon
      /#23145514

      Какое?

      • GospodinKolhoznik
        /#23145632 / +1

        Пусть функция f(X) работает так: ей на вход подаётся множество X, она делит его на 2 множества - в XA все элементы меньше или равны первого числа a исходного множества X, а во втором XB больше этого числа. Такое деление выполненяется за линейное время. Ключевой момент: если длина XA равна a, то в нем нет минимального числа и искать надо в XB. Таким образом функция знает что ей вызывать дальше рекурсивно - f(XA) или f(XB). "Легко видеть" (на самом деле нет), что сложность алгоритма O(N) так как алгоритм проходится сначала по всему множеству линейное время, потом по его половине, а вторую половину игнорирует и т.д. N + N/2 + N/4 + N/8 +... = 2*N т.е. время линейное.

        • RussianDragon
          /#23145648

          Такой вариант решения приведен в статье. Только с учетом, что множество не является отсортированным. Сортированное вообще не проблема перебрать, только сортировка занимает кучу времени.

          • GospodinKolhoznik
            /#23145664

            Виноват, зевнул. Чукча не читатель...

            Я думал у вас скорость O(N *ln(N)), а не просто O(N).

  2. BugM
    /#23145518 / +1

    Я наверно что-то не понял, но где простейшие и оптимальные варианты?

    Для случая когда мы ожидаем такое число ближе к началу:

    for(int i=0; i<arr.length; ++i) {
      if(arr[i] != i)
        return arr[i-1]+1;
    }


    Для случая когда мы ожидаем его ближе к концу бинарный поиск по такому же условию.
    O(N) и O(log(N)) соответвенно. По памяти везде O(1)

    Краевые условия не писал, все понятно. Код для демонстрации идеи.

    • RussianDragon
      /#23145542 / +1

      Это всё здорово, если у на отсортированное множество… А рассматриваются варианты — где значения лежат как попало. Сортировка рассматривается как раз в конце. И считается её производительность.
      т.е. { 0, 12, 4, 7, 1 } здесь MEX равен 2-м.

      • BugM
        /#23145560

        Тогда так www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array
        A O(n) time and O(1) extra space solution

        Идея заметно проще и оптимальнее чем у вас.

        • RussianDragon
          /#23145574

          Что строим? Как строим? Что O(N)?

          • BugM
            /#23145590

            Я поправился. Был сначала не прав.

            Я начал рассказ с конкурса на OZON в котором я пробовал участвовал, сделав «предварительный вариант» алгоритма просеиванья, приз за него я так и не получил, OZON счел его неудовлетворительным… По каким именно причин — он так и не сознался… До и кода победителя я не видел. Может у кого-то есть идеи как можно решить задачу поиска MEX лучше?

            Я бы ваше решение тоже не зачел. Оно откровенно неоптимальное.

        • RussianDragon
          /#23145626

          Тогда так www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array
          A O(n) time and O(1) extra space solution

          А Вы сами это решение читали?

          Чувак 4 раза перебирает массив

          // Check if 1 is present in array or not
              for(int i = 0; i < n; i++)
              {
                  if (arr[i] == 1)
                  {
                      ptr = 1;
                      break;
                  }
              }
             
              // If 1 is not present
              if (ptr == 0)
                  return 1;
             
              // Changing values to 1
              for(int i = 0; i < n; i++)
                  if (arr[i] <= 0 || arr[i] > n)
                      arr[i] = 1;
             
              // Updating indices according to values
              for(int i = 0; i < n; i++)
                  arr[(arr[i] - 1) % n] += n;
             
              // Finding which index has value less than n
              for(int i = 0; i < n; i++)
                  if (arr[i] <= n)
                      return i + 1;

          4 раза!
          О каком O(n) вообще может идти речь?

          • BugM
            /#23145628

            4 раза!
            О каком O(n) вообще может идти речь?

            Вы точно знаете что означает O(N)?

            • RussianDragon
              /#23145638 / -3

              Вы точно знаете что означает O(N)?

              В моем понимании — это количество итераций которое нужно совершить. Обычно рассматриваем самый кривой случай. Так вот коде парня аж 4 прохода по массиву. Может с точки зрения математики — это не в счет, но вот сточки зрения реальной задачи — бегать по сто раз по массиву не выглядит перспективной идеей.

              • BugM
                /#23145656 / +1

                А если все таки прочитать ну хотя бы википедию?
                en.wikipedia.org/wiki/Big_O_notation

                • RussianDragon
                  /#23145668 / -3

                  Так. Получается по вашему — любая функция которая принимает одни аргумент — это O(n)?

                  Я хоть как-то попытался это рассчитать в базовых операциях.

                  • vkni
                    /#23145826 / +5

                    Нет, это оценка с точностью до константы. Применяется к последовательностям. Например, последовательность

                    S n = n + 22 


                    при больших n у нас приблизительно S n = const*n

                    Но то же самое справедливо и для последовательности

                    S2 n = 2*(n + 22) 


                    При больших n аналогично S2 n = const*n

                    Таким образом, обе эти последовательности имеют асимптотическое поведение O(n).

                    Это, кстати, к вопросу о том, нужен ли университет для программирования.

                • rrrad
                  /#23145712

                  А вы статью читали? Автор пишет O(n*3), это прямое свидетельство в том, что он не понимает О-нотации.

                  Строго говоря, алгоритмы, которые модифицируют исходный массив (в особенности - разрушают, как это делает предложенный алгоритм со сложностью O(N) и якобы О(1) по памяти), являются O(N) по памяти, т.к. для их использования вам придётся сделать копию массива. И если с сортировкой, эти данные могут еще понадобиться (и тогда этот алгоритм будет самым выгодным), то с изменением знака (кстати, использование знакового разряда, как мне кажется, ничем не отличается от использования отдельно выделенной битовой матрицы размера N).

                  Кстати, еще одно замечание для автора касательно второго варианта (где выделяется второй массив). Нам не надо искать максимум для выбора его размера, мы и так знаем, что результат находится в диапазоне от 0 до n, поэтому и массив нужен размера n, инициализировать можно нулями (при выделении ОС отдаст именно такую память, может даже время не потратиться, если будет заранее доступен кусок обнулённой памяти), а далее просто проходимая по массиву, отбрасывая числа >= n, проставляя 1 по индексу для чисел от 0 до n-1. Дальше быстрый проход по этому массиву до первого нуля.

                  • RussianDragon
                    /#23145738 / -1

                    Автор пишет O(n*3), это прямое свидетельство в том, что он не понимает О-нотации.


                    Ок. Предположим, что я не понимаю нотации.
                    Но вариант O(n) меня вообще не устраивает. Т.к. в таком случае непонятно какой размер у O. В итоге я стараюсь считать шаги в максимально простых действиях: в проверках, в бинарных расчетах. Что-то более менее понятное по скорости. И что позволяет хоть как-то сравнить три подхода.

                    • vkni
                      /#23145842 / +2

                      Что-то более менее понятное по скорости. И что позволяет хоть как-то сравнить три подхода.


                      Это не позволяет, увы. Стоимости разных операций в процессоре совершенно разные. Причём это варьируется от процессора к процессору. Часть операций использует кэш-память, что резко ускоряет процесс в ряде случаев, раз в 40 запросто.

                      Поэтому модель RAM машины на современных десктопах/серверах работает с трудом. Соответственно, когда вы не используете O-нотацию, вы чаще всего получаете ошибку превышения точности (за которую тех же физиков «бьют линейкой по голове» :-)).

                    • rrrad
                      /#23145984 / +4

                      О-нотация — это асимптотика, её используют для выбора алгоритма когда понятно, что потребуется обрабатывать много данных, т.к., грубо говоря, если завтра объём обрабатываемых данных возрастёт в 50 раз, то не имеет значения, что алгоритм с O(n) реально выполняет 10*n операций, т.к. время исполнения этого алгоритма растёт гораздо слабее чем у алгоритма с O(n^2). На малых объёмах на асимптотическую сложность не смотрят, здесь всё решают реальные замеры. И не редкая ситуация, когда алгоритм с худшей асимптотической сложностью имеет меньший коэффициент, чем растущий медленнее. Это одна из причин, по которой худшие по О-нотации алгоритмы изучают. И именно это является причиной того, что библиотечные реализации сортировки, как правило, содержат две реализации — быструю сортировку и один из алгоритмов (какой конкретно не помню, подозреваю что пузырёк) с квадратичной сложностью. При чём выбор того, на каком количестве элементов следует переключаться на быструю сортировку, скорее всего продиктован реальными замерами.

                  • BugM
                    /#23145748 / +1

                    Строго говоря, алгоритмы, которые модифицируют исходный массив (в особенности — разрушают, как это делает предложенный алгоритм со сложностью O(N) и якобы О(1) по памяти), являются O(N) по памяти, т.к. для их использования вам придётся сделать копию массива.

                    Массив в конце можно восстановить. Никаких необратимых изменений мы в нем не делаем.
                    Можно сказать что или массив можно менять или не thread safe или O(N) по памяти. Так совсем честно будет.

                    • vkni
                      /#23145836

                      В представленном виде мы явно делаем необратимые изменения. См.

                          // Changing values to 1
                          for(int i = 0; i < n; i++)
                              if (arr[i] <= 0 || arr[i] > n)
                                  arr[i] = 1;


                      Наверное, как-то можно исхитриться и при определённой статистике данных как-то сделать эти манипуляции обратимыми. Но я не вижу пока как.

                      • BugM
                        /#23146124

                        Задачка у автора без отрицательных чисел. В ней все обратимо.
                        Чуть-чуть переписать и будет обратимо.

  3. ganqqwerty
    /#23145588

    Спасибо за то, что собрали варианты вместе. По поводу оценки сложности, я заметил в статье некоторые проблемы в нотации. Буква О введена именно для того, чтобы показывать характер роста вычислений. Ровно один проход, ровно шесть проходов или ровно двадцать проходов - это все O(n), константные множители отбрасываются.

    Аналогично с квадратами - O(n^2) это и есть O(n^2). Вы можете посчитать количество вычислений точнее и сказать, что их будет ровно 100n^2+72n+21, но сложность в этом случае будет O(n^2).

    Кажется, для точного количества вычислений используется буква T у Кормена.

    • RussianDragon
      /#23145634

      Надо поискать будет эту нотацию, спасибо.

  4. siarheiblr
    /#23145650 / -1

    А почему бы не сложить числа в двоичную кучу? Строим кучу по возрастанию, потом вытаскиваем оттуда дважды минимальный элемент и смотрим, насколько полученные числа отличаются. Если больше чем на единицу то прибавляем к минимальному значению 1 и вот ответ. Иначе достаём следующий минимальный элемент и сравниваем с предыдущим.

    О(n) на построение и О(n) сравнений в худшем случае. В итоге сложность О(n).

    • RussianDragon
      /#23145660

      Строим кучу по возрастанию, потом вытаскиваем оттуда дважды минимальный элемент и смотрим, насколько полученные числа отличаются.

      Т.е. мы сортируем массив? Это «дорогая» операция если что.

  5. yizraor
    /#23145686

    Ужасный пост.
    О проблемах с O-нотацией уже сказали, не буду повторять.
    Скажу лучше про затраты памяти. То, что некоторые быстрые алгоритмы требуют дополнительной памяти — это приемлемо. Как говорится, "за всё надо платить", за скорость в том числе. (и наоборот — за экономию памяти алгоритмы, как правило, платят скоростью)
    Стёб же над "математиками" — совершенно неуместен.


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


    Примерно так:


    1. Тривиальное решение ("в лоб") — не требует дополнительной памяти, но является квадратичным — O(n^2). Впрочем, производительность приемлема на крошечных множествах.
    2. Решение, основанное на сортировке — работает с асимптотикой используемого алгоритма сортировки, т.е. не быстрее чем O(n*log_n). Алгоритм не зависит от размерности рассматриваемого множества.
    3. Просеивание — работает с асимптотикой O(n), но требует дополнительной памяти O(m), где m — размерность множества. Память O(m) серьёзно ограничивает применимость алгоритма на практике, тем не менее — где-то и он может пригодиться.

    P.S.:
    Вижу алгоритм, работающий за O(n), с дополнительной памятью тоже O(n).
    (использовать хэш-таблицу)

    • RussianDragon
      /#23145752

      Вижу алгоритм, работающий за O(n), с дополнительной памятью тоже O(n).

      Hash таблицы хороши если мы пытаемся найти значение которое точно есть, или то которого нет. В других случаях нам всё равно придется устраивать перебор значений. Что в целом — та же сортировка…

      • sophist
        /#23145862 / +1

        А разве нам не достаточно находить, значение точно есть или его нет? Перекладываем значения в HashSet и ищем в нём числа по порядку, начиная с 0. Первое отсутствующее значение и будет ответом.

        • RussianDragon
          /#23145894

          Перекладываем значения в HashSet и ищем в нём числа по порядку, начиная с 0.
          Ну как бы это цикл по элементам которые еще сложнее чем массив.
          Чуть HashSet 0 быстрое нахождение элемента, если он есть.

          • sophist
            /#23145908 / +1

            Но в этом цикле и вставка, и проверка наличия занимают O(1) времени. Итого O(n).

      • yizraor
        /#23145946

        Hash таблицы хороши если мы пытаемся найти значение которое точно есть, или то которого нет.

        Так нам это и нужно!
        Делаем в два прохода по набору исходных данных.
        Проход 1 — запихиваем всё в хэш-таблицу.
        Проход 2 — для каждого значения x в исходном наборе данных проверяем наличие в хэш-таблице значения, равного x+1. Если x+1 не найдено — значит, это потенциальное решение задачи.
        Конечным результатом будет минимум между всеми отсутствующими в хэш-таблице x+1. Дополнительно надо проверить минимальное и максимальное значения в исходных данных (на любом из проходов).


        P.S.:
        Таким алгоритмом решается целый класс задач.
        Вот ещё один пример: "найти в массиве все пары чисел, сумма которых равна числу m".

        • Politura
          /#23146048 / +2

          Смотрите, в случае хэш-таблицы, нам необходимо высчитывать хэш, пусть и за константное время, затем еще проходить по нескольким ячейкам таблицы когда у нас коллизии с одинаковым хэшем для разных значений, пусть как-бы тоже за константное время. Однако если в качестве хэша использовать само значение элемента и хэш-таблицу сделать размером с оригинальную таблицу, то у нас не будет ни коллизий, ничего высчитывать не надо: просто идем в ячейку с индексом самого значения… и получаем вместо хэш таблицы обычный массив. :)

          Короче, просто доп. массив такого-же размера, что и оригинальный, инициированный каким-то значением, которого нет в оригинальном наборе, хоть -1, хоть INT_MIN, не важно, а дальше с ним работаем, как с хэшем в вашем варианте.
          И тут встает вопрос: но если у нас индексы совпадают со значением, зачем в этом массиве хранить целые числа, почему не хранить просто булевые значения: true/false? Хоп и мы пришли к алгоритму просеивания :)

          • yizraor
            /#23146860

            Да, Вы правы.
            После Вашего комментария, я понял идею оптимизированного алгоритма просеивания.
            (тяжело понимать автора — у него вроде как берётся массив в размере множества; а Вы объясняете с оптимизацией по дополнительной памяти до размера входных данных)

          • yizraor
            /#23146902

            О, кстати, вижу что я ошибся при оценке авторского алгоритма просеивания. Там же из-за инициализации массива будет асимптотика не O(n), а O(max(n,m)). Можно упростить до O(m), если во входных данных нет повторений, т.е. n<=m.


            А хэш-таблицы не стоит выбрасывать из рассмотрения. И вот почему — алгоритм просеивания (хоть авторский, хоть оптимизированный) рассчитан только на работу со множеством целых чисел!
            А что если множество состоит из других объектов? Да, к этому случаю возможно адаптировать просеивание, если назначить каждому объекту какой-то числовой (порядковый!) индекс. Для этого нужно определить порядок объектов во множестве — т.е. выполнить сортировку множества перед просеиванием. И сортировка эта будет стоить минимум O(m*log m), ухудшая асимптотику всего алгоритма.
            Правда, если планируется выполнять алгоритм просеивания много раз на различных входных данных (но на одном и том же множестве объектов), то повторять сортировку множества не нужно — и получаем довольно быстрый алгоритм с предварительным расчётом.

    • luckman
      /#23145906 / +4

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

      Тогда при первом проходе мы просто забиваем на числа, которые больше n — нас они не интересуют.

      Вот, кстати, почему решение автора кривое. На тесте {1, 1000000000} эта версия алгоритма просеивания просто упадёт по памяти.

      • RussianDragon
        /#23145928

        Принял и согласен, можно игнорить числа больше длинны множества. Т.к. они явно нам не интересны. Поправлю

    • wataru
      /#23147674

      P.S.:
      Вижу алгоритм, работающий за O(n), с дополнительной памятью тоже O(n).
      (использовать хэш-таблицу)

      Да не надо хеш-таблицы даже. Чтобы найти минимальнео число, не встречающееся среди заданных n наужен лишь битовый массив на n бит.

  6. DSarovsky
    /#23145694

    А нельзя что-то типа вектора-индикатора прикрутить? Алгоритм примерно такой:
    1) Выделить массив bool-переменных размера исходного массива (можно сжать и получить size/8 байтов). Это O(1) по времени, но O(n) по памяти.
    2) Пройти в цикле исходный массив, заполняя в true соответствующие индексы этого bool-массива. Это O(n).
    3) Пройти bool-массив, индекс первого false — это ответ. Тоже O(n).
    Итого O(n) и даже константа небольшая.

    • RussianDragon
      /#23145722

      Это и есть «просеиванье». там как раз создается boolean массив…

      • DSarovsky
        /#23146426

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

    • vkni
      /#23145816

      Это «просеивание». Вообще задача олимпиадная, а у них свои погремушки, часто редко встречающиеся в нормальной жизни. Например, если массив можно «уничтожить», то есть, изменить до неузнаваемости, то можно сделать O(n) по времени и O(1) по памяти (см ссылку выше).

  7. AVI-crak
    /#23145824

    Меня вот удивляет одна вещь, соревнования по скорости сортировки максимально оторваны от реальности, и всем на это глубоко пофиг. Сортировка одного массива — это почти академическая задача. Она требуется всего пару раз в жизни…

    В реальности гораздо чаще нужно сортировать многомерный массив — результат сканирования таблиц, или любого большого количества данных хоть в какой-то структуре хранения. Массив в виде адресов, индексов, числовых и текстовых значений… То-есть изначально разношорстный комок данных.
    Для этого есть готовые алгоритмы сортировки, но видимо они слишком сложны для рассмотрения.

    • RussianDragon
      /#23145828 / -3

      Для этого есть готовые алгоритмы сортировки, но видимо они слишком сложны для рассмотрения.

      Все алгоритмы сортировки сводятся фактически к quicksort. Ничего быстрее пока не придумали.

      • JekaMas
        /#23145898 / +2

        Это не так. Вопрос, какие случаи мы хотим лучше и какие данные мы хотим. Иногда и merge, иногда и хитрые комбинации.

        Про быстрее. От данных зависит. Вдруг мы целые сортируем. Тогда и counting, и Radix за линейное можно.

  8. C-4
    /#23145884

    Уже многие отметились. Попробую предложить что-то новое. Ищем за один проход. Перебираем поэлементно. Каждый элемент i образует либо новую цепочку LinkedList, либо присоединяется к существующей. Если есть цепочка с последним элементом равным i-1, то элемент присоединяется к ней в конец (становится ее последним элементом), если есть цепочка c первым элементом i+1 то в начало (становится ее первым элементом). Если нет ни одной такой подходящей цепочки — создается новая.
    В третьем примере множества a={11, 10, 9, 8,15,14,13,12,3,2...106,104} последовательно перибирая элементы, дойдя до a[3] будем иметь одну цепочку от 8 до 11, на a[4] будет уже две цепочки {8:11}, {15}, a[7] — две цепочки {8:11}, {12:15} и т.д.
    Для быстрого поиска нужной цепочки, корни всех цепочек будут образовывать дополнительное сопоставление число в корне — указатель цепочки, а вершины всех цепочек сопоставление число в вершине — указатель цепочки. Все цепочки также должны быть упорядочены по возрастанию своих корней. Если элемент подходит для конца одной цепочки и начала другой, то две цепочки склеиваются в одну через этот элемент.
    После перебора всех элементов массива, будет образован набор цепочек. В любом случае первый отсутствующий элемент будет определен как либо:
    а) n-1, где n первый элемент цепочки, при n-1 != 0,
    б) либо k+1, где k — последний элемент первой цепочки.
    Объяснение получилось громоздким, но думаю плюсы у данного алго найдутся: не требуется сортировка. Можно сделать за один проход. По памяти не требователен (сумма длин всех цепочек равна количеству элементов, правда нужна доп. память на быстрый поиск по корням и вершинам). Должен любить работать с множествами, где отсутствующих элементов почти нет.

    • RussianDragon
      /#23145924 / +1

      прочитал несколько раз. Понял только, то что очень много памяти потребуется…

      • C-4
        /#23150368

        Да, согласен, описание такое себе. Что же, выложил на github эту версию алгоритма. Поиск за O(n) без всяких множетелей. Потребление памяти можно довести практически до константных значений. Это не продакшен версия, но ее можно доработать, что бы она работала в динамике.

    • VaalKIA
      /#23146090

      Если у вас данные такие: {1, 3, 5, 7, 9, 11}, экономично получается? Как бы ищут универсальный алгоритм…

      P. S. Надоело час ждать, напишу тут.

      Можно уменьшить количество памяти для просеивания. Посчитать сколько чисел одинаковой разрядности (для двоичных трёхразрядных: 00X — 2 числа, 0XX — 4, XXX — 8) за первый проход и потом взять группу, где количество будет меньше максимума и уже от неё плясать. Подпортит статистику одинаковые числа, но «меньше», в любом случае гарантирует наличие вакансии.
      По памяти расходы смешные, в худшем случае теряем только этот проход.

    • BugM
      /#23146138

      Для быстрого поиска нужной цепочки, корни всех цепочек будут образовывать дополнительное сопоставление число в корне — указатель цепочки, а вершины всех цепочек сопоставление число в вершине — указатель цепочки. Все цепочки также должны быть упорядочены по возрастанию своих корней. Если элемент подходит для конца одной цепочки и начала другой, то две цепочки склеиваются в одну через этот элемент.

      Вот эта часть даст квадрат или n*logn в лушем случае если хорошо написать.
      На данных вида:
      1-3-5-7-9-2-6-4
      Не годится. Просто отсортировать даст тоже самое…

    • mk2
      /#23146554

      Учитывая, что у вас фактически используется O(n) памяти, просеивание выходит лучше.

  9. MichaelBorisov
    /#23146024 / +1

    Спасибо, автор. Интересная идея алгоритма поиска.

    В контексте исходной «озоновской» задачи можно попытаться ввести в структуру данных какие-нибудь инварианты, которые поддерживаются при её работе и облегчают выполнение операций.

    В задаче требуется сделать только операции добавления и «шифрования». Оставим пока в стороне «шифрование» и рассмотрим только структуру данных с операцией добавления.

    Если исходная база была пустой, то новый id пользователя всегда равен количеству уже зарегистрированных, и никакой поиск делать не надо. Таким образом, отсутствие пропусков в нумерации — это инвариант, которым можно воспользоваться.

    Дырки в нумерации могли бы образоваться за счёт удаления пользователей, но удаление нас реализовать не просят. Возможно, это от «Озона» специальная ловушка, и они ожидают, что вы: 1) зададите вопрос, а точно ли им не нужно удаление; 2) по своей инициативе сделаете удаление.

    Если делать удаление — то массив занятых id останется отсортированным. А в отсортированном случае можно найти пропуск быстрее, чем за O(n), а именно, за O(log(n)). Смотрим на средний элемент массива и проверяем, есть ли в первой половине пропуски. Критерий: values[n/2]>n/2. Если есть — ищем дальше в первой половине массива, в противном случае — во второй.

    Таким образом, отсортированный массив id — это второй возможный инвариант.

    Теперь рассмотрим «шифрование». Даже если в массиве id до «шифрования» не было пропусков — то после «шифрования» они появятся. Но операция «шифрования», вероятно, выполняется реже, чем добавление новых пользователей. Поэтому есть смысл делать сортировку массива id при «шифровании», тогда для поиска свободного id будем всегда иметь отсортированный массив занятых id.

    Можно также попытаться воспользоваться свойствами операции «исключающее или» для облегчения сортировки. Подозреваю, что, если исходный массив был отсортирован, а потом все его элементы сложили по модулю 2 с константой — то отсортировать полученный массив можно быстрее, чем в общем случае.

    • mk2
      /#23146516 / +1

      В контексте алгоритмических задач — предположение «операция шифрования выполняется реже» неверно. Напротив, решение должно выполняться за заданное время даже при последовательности операций «добавление-шифрование-добавление-шифрование».

      И поэтому требуется придумать структуру, в которой mex фактически выполняется за сублинейное время. И я бы попробовал дерево по двоичным разрядам с отложенной операцией xor. Да, это кажется сработает. Асимптотика добавления нового числа O(log m), шифрования вообще O(1). Правда, нахождение текущего ID пользователя будет занимать O(n), но эту операцию от нас и не требуют. А в конце за тот же O(n) находим все ID.

      • MichaelBorisov
        /#23148662

        Я тоже думал предложить отложенный xor. Более того, несколько операций «шифрования» эквивалентны одной, у которой ключ — исключающее «или» от всех предыдущих ключей.

        Проблема в том, что отложить xor можно только до следующего добавления, так как до и после ксорки минимальные свободные ID различаются.

        • wataru
          /#23148758

          Да нет же: вместо шифрования базы можно шифровать входные данные. Просто поддерживайте, что в базе хранится то, что должно, если бы все элементы в базе про-xor-ились с заданным k. При добавлении числа x, добавляйте x xor k. При шифровании базы обновляйте k.

        • mk2
          /#23148894

          Учитывая, что у нас дерево, то в каждом поддереве хранится число, на которое это поддерево нужно xor-нуть. И когда спускаемся, продвигаем это число в child nodes.
          Правда как подсказали ребята из Озона, отложенный xor не нужен.

  10. mk2
    /#23146512

    Задачу также можно решить за O(n*logn) времени и O(1) памяти с помощью двоичного поиска без сортировки. Для этого воспользуемся тем, что все элементы в множестве уникальны. Поэтому мы можем просто взять и за один проход подсчитать количество элементов, меньших или равных k. Если это количество меньше k, значит MEX <= k.

    • RussianDragon
      /#23148648

      На несортированном множестве мы ищем элемент меньше k.
      Что за k? И каково будет минимальное отсутствующее число?

      • MichaelBorisov
        /#23148680

        k можно взять равным половине количества учётных записей пользователей. Найдя кол-во чисел, меньших k, можно установить, находится ли минимальный отсутствующий элемент в первой половине массива. Если да — то применить этот же алгоритм рекурсивно для первой половины массива. Если нет — то применить его для второй половины массива и т.д.

        Очень хорошая идея, кстати. По-моему этот алгоритм имеет сложность O(n), а не O(n*log(n)). И по сравнению с другими описанными здесь алгоритмами с O(n), он по памяти имеет сложность O(1) и не портит исходный массив. Так что очень привлекательный алгоритм.

        • RussianDragon
          /#23148914

          так массив не сортирован. Тогда, сначала, его нужно отсортировать… что бы это работало. Кстати, сверху описан подобный алгоритм поиска именно на несортированном массиве.

      • wataru
        /#23148768

        Это не классический бинпоиск в массиве, а дихотомия или же "бинарный поиск по ответу". Взяв любое k и подсчитав, сколько элементов в массиве <= k мы можем понять если там дырка или нет (т.е. ответ < или > k). Это позволяет отбросить половину возможных ответов.


        Грубо говоря, есть булевый массив, который заполнен true для индексов больше ответа и false для индексов меньше ответа. Мы делаем бинпоиск в этом массиве. Но вместо вычисления всего массива сразу мы вычисляем только те элементы, на которые смотрит бинпоиск. Вот и получается O(n log n). log n итераций бинпоиска, каждая за O(n) вычисляет элемент ответа.

        • MichaelBorisov
          /#23148848

          Вот и получается O(n log n). log n итераций бинпоиска, каждая за O(n) вычисляет элемент ответа

          По-моему здесь всё-таки сложность O(n), а не O(n log n), так как поиск по оставшейся половине требует просмотра каждый раз в 2 раза меньшего кол-ва элементов. И это существенно. Ведь сумма 1/2+1/4+1/8+… = 1. Общее количество просмотренных элементов не превысит n независимо от того, сколько раз алгоритм делил массив пополам.

          • wataru
            /#23149724

            Нет, вам надо каждый раз просматривать все n чисел, чтобы ответить на вопрос: "сколько чисел <= k". Вы же исхожный массив не сортируете, не трогаете, а только просматриваете. И это k меняется в бинпоиске.

            • MichaelBorisov
              /#23152196

              Хорошо, уточню, ошибся. Первый раз вы просматриваете n элементов, потом n/2, потом n/4 и т.д. Сумма 1+1/2+1/4+1/8+… = 2.
              Так что максимальное суммарное количество элементов, которые придётся просмотреть, равно 2n. А это означает O(n), не так ли?

              Если бы было O(n log n) — то были бы другие зависимости. Например, для n=10 потребовалось бы 10 итераций, для n=100 — 200 итераций, для n=1000 — 3000 итераций и т.д., то есть количество итераций растёт быстрее, чем const*n. Или, что то же самое, отношение количества итераций к n растёт неограниченно (хотя и медленно).

              В вашем же случае неограниченного роста отношения количества итераций к n нет, отношение остаётся константой, не зависящей от n.

              • wataru
                /#23152228

                Первый раз вы просматриваете n элементов, потом n/2, потом n/4

                Опишите весь алгоритм. Почему потом просматривается n/2 элементов а не n?
                Обсуждаемый в этой ветке алгоритм каждый раз просматривает все элементы, чтобы подсчитать, сколько из них меньше текущего перебираемого бинпоиском числа.

                • MichaelBorisov
                  /#23152706

                  Вы правы, я ошибся. Конечно же, надо просматривать весь массив каждый раз, а не его часть, как мне первоначально показалось. Тогда, как вы и написали, будет O(n log n).

  11. lair
    /#23146604

    Многие придрались к O(n), мол все алгоритмы O(n) и по фигу, что «O» везде разное и не даёт фактически сравнить количество итераций.

    В задаче от Озона явно написано "наиболее оптимальное с точки зрения асимптотики". Асимптотика — это O-нотация.


    мы рассматриваем случай когда исходное множество НЕупорядоченное.

    В задаче от Озона явно сказано: реализовать структуру [данных] с операцией добавления нового пользователя. Это значит, что вам недостаточно сделать поиск по множеству, вам еще и нужно сделать такое множество, в котором было бы эффективное добавление (и, до кучи, эффективное "шифрование").


    Самый быстрый алгоритм сортировки — это «quicksort» (быстрая сортировка), которая имеет сложность в T1(n log(n)).

    Это утверждение неверно. Быстрая сортировка (а) имеет сложность O(n log n), а не (какое-то там) T(n log n), и, что важнее (б) "самая быстрая" только для общего случая (в частности, для целых чисел есть сортировки O(n+r), где r — диапазон).

    • RussianDragon
      /#23148520

      В задаче от Озона явно написано «наиболее оптимальное с точки зрения асимптотики». Асимптотика — это O-нотация.


      Для меня, как для разработчика, важнее всего скорость и объем оперативной памяти с которой будет выполняться алгоритм.
      Мне кажется, OZON, и имели всё же «скорость работы», пусть у упаковали это в описании O-нотации. Ибо решается практическая, а не теоретическая задача.

      Это значит, что вам недостаточно сделать поиск по множеству, вам еще и нужно сделать такое множество, в котором было бы эффективное добавление (и, до кучи, эффективное «шифрование»).

      Я не увидел в контексте этой задачи, что необходимо сделать собственную структуру данных.
      Мне вообще не понравилось как поставлено условие. Что я могу сделать добавление данных как мне «удобно». Может мне удобно так, что без гайда по API вообще не понятно будет. А тестировать как? К самой загрузке данных — много вопросов. Они пишут про ограничение объема оперативной памяти, но не говорят, сколько она записей должна вмещать…

      В общем мне сама формулировка вообще не нравится, а связаться с авторами конкурса вообще нельзя по-человечески.

      Это утверждение неверно. Быстрая сортировка (а) имеет сложность O(n log n), а не (какое-то там) T(n log n), и, что важнее (б) «самая быстрая» только для общего случая (в частности, для целых чисел есть сортировки O(n+r), где r — диапазон).

      На самом деле «просеиванье» тоже можно назвать «сортировкой», тут я согласен.

      • lair
        /#23148558 / +1

        Для меня, как для разработчика, важнее всего скорость и объем оперативной памяти с которой будет выполняться алгоритм.

        Ну так ровно для этого O-нотация и нужна — чтобы получить оценки скорости и объема памяти. А потом вам поможет только профилирование.


        Я не увидел в контексте этой задачи, что необходимо сделать собственную структуру данных.

        Там прямым текстом написано: "реализовать структуру, выполняющую два вида запросов". И это, кстати, очень узнаваемая формулировка, если вы читали или слушали Седжвика.


        На самом деле «просеиванье» тоже можно назвать «сортировкой», тут я согласен.

        Нет, нельзя назвать. Так что я не понимаю, с чем вы согласны.

        • RussianDragon
          /#23148632

          Нет, нельзя назвать. Так что я не понимаю, с чем вы согласны.

          Это почему нельзя?
          Мы получаем упорядоченную структуру, в которой точно будет сохранен факт наличия данных в изначальным множестве. По факту это усеченная counting sort или сортировка подсчетом.

          • lair
            /#23148644

            Мы получаем упорядоченную структуру

            А вы в ней храните m флагов или n?

            • RussianDragon
              /#23148676

              Да, признаю. Сейчас это алгоритм изменился в угоду быстродейственности и объему памяти в рамках задачи MEX. Изначально я находит максимально число в массиве и сам boolean-массив был длинной равный максимальному числу из множества. И мы как раз получали возможность узнать пустые значения на всем диапазоне изначального множества.
              В процессе споров в комментариях я оптимизировал выборку первого элемента, сделал массив длинной с изначально множество, а значения больше это длинны игнорировал. Чем по факту “сломал” его переиспользования для поиска “второго” пустого значения. Тут я признаю, что поддался на уговоры.
              Так что в целом справедливы оба решения. Если нам нужно выбрать только одно число mex из случайного множества, то текущий код в статье оптимальный. Если мы хотим переиспользовать полученный boolean-массив, то нужно вернуть вариант, где изначально ищется max на исходном множестве.

              И, кстати, к разговору об O, мне здесь упорно доказали, что в данном случае операция поиска MAX, просеиванье и поиска по просеянным данным – это O(n). Что хоть и правильно с точки зрения теории, но мне в корне не нравится для оценки реальной бытродейственности.

              • lair
                /#23148714 / +1

                Что хоть и правильно с точки зрения теории, но мне в корне не нравится для оценки реальной бытродейственности.

                Оно, конечно, может вам не нравиться, но если внимательно посмотреть, у вас выбор не между разными O(n), у вас выбор между логарифмическим, линейным, линейным от другого порядка, O(n log n). Вот когда между ними выбор сделан, тогда уже можно на коэффициенты смотреть.

        • wataru
          /#23148772

          Нет, нельзя назвать. Так что я не понимаю, с чем вы согласны.

          Это просеивание — это по сути сортировка подсчетом, слегка упрощенная (выкинуть слишком большие ненужные элементы и забить на повторения).

  12. teology
    /#23147240

    Сама по себе задача MEX банальна. Гораздо интереснее задача Ozon-MEX, которая включает в себя шифрование. Будем решать Ozon-MEX.
    Алгоритм 1. Пусть обновился ключ шифрования и он равен x. Обратим внимание, что при шифровании пользователь с id=x принимает новый id, равный 0, а в более общем случае заметим, что если у пользователей ряд старших бит совпадает со старшими битами ключа, то новый id будет близок к 0.
    Это все ведет к идее алгоритма поиска отсутствующих id пользователей, близких к текущему ключу x. Так как ключ на практике намного короче id (занимает O(k) памяти, k<<n). Для примера k=32, n=300 000 000 (русскоговорящее население планеты).
    Делаем перебор в лоб, начиная со значения ключа x. Если пользователь id=x существует, то изменяем младшие биты. И так далее. Перебор в лоб имеет сложность O(2^k) по быстродействию и O(1) по памяти. С ключом длиннее примерно 32-бит алгоритм проигрывает по быстродействию алгоритму «просеивания» по быстродействию, но не по памяти.

    Алгоритм 2. Мы понимаем, что ключ шифрования меняется гораздо реже, чем регистрируются пользователи. Следовательно, образуются частично упорядоченные наборы id, которые впоследствии «разрушаются» новым ключом шифрования.
    Мы хотим иметь ключ длиной 512 бит, но при этом не перебирать 2^512 вариантов. Мы можем сохранить в памяти диапазоны id и сохранить старый ключ (компрометировать его). В принципе это нормально, но тогда важно генерировать новые ключи случайным генератором.
    Допустим, выдали пул id от 0 до 10000, ключ был x=x1. Пришел запрос на шифрование новым ключом — сохраняем значения [0, 10000, x1], принимаем новый ключ x2, который пока нельзя компрометировать.
    Зная предыдущие наборы [0, max1, x1], [0, max2, x2],… и текущий ключ x, можно находить «пустоты» намного быстрее, чем в алгоритме 1. Начало диапазона всегда 0, поэтому, в принципе, можно не сохранять в памяти.
    Сам алгоритм заключается в том, чтобы не перебирать все комбинации как это делается в алгоритме 1. Оставляю возможность сформулировать алгоритм кому-то другому, мне дальше неинтересно.

  13. gektor2510
    /#23147274 / +1

    Добрый день, @RussianDragon!
    Правильных решений в этой задаче было много. По правилам конкурса, мы выбирали одно самое оригинальное. Победителем и обладателем суперприза стал участник с наиболее оптимальным и оригинальным кодом.
    Вы, к сожалению, не так поняли задачу. Требовалось подготовить структуру, которая будет эффективно отвечать на все запросы участников. Учитывая, что запросов очень много, ваше решение на каждый запрос будет делать одни и те же действия. Одним из оптимальных решений может быть trie (Бор в русскоязычной литературе) —  структура для строк, которая позволяет нам добавлять строки за их длину. Давайте хранить все числа в двоичном виде trie, тогда добавление будет работать за O(log(n)), где n — максимальное число в структуре. Операцию же шифрования можно реализовать за O(1), так как a xor b xor c = a xor (b xor c). Теперь насчет операции нахождения mex. Его можно также найти за O(log(n)) просто спускаясь по бору и идя в нужную ветку (вы проверяете, чему равен этот бит в кодировании и если он 0 — идете в меньшие числа, иначе — в большие). Итого это решение уже работает за N*log(max).
    Ваше же решение в любом случае будет работать за O(N * N), что гораздо дольше. Это решение уже почти оптимально, но так как его написали достаточно много участников, мы также смотрели на более быстрые и оригинальные.

    • RussianDragon
      /#23148562 / -1

      Вы, к сожалению, не так поняли задачу.

      Верю.
      Но вы дали ограничение по скорости и по памяти, но не сказали объем данных, хотя бы примерно. 10, 20, 100, 1000 или 1 000 000 000. Тогда можно было бы хоть как-то тестировать свой алгоритм по условиям задачи, а учитывая, что подача всего одна узнать, что конкретно от меня хотят — целая проблема. Хотя бы дали файлик с записями и сказали — вот «ребята» txt с изначальными данными — выкручиваетесь. А может вам хватило бы рандомной генерации данных (без повторений)… В обще и целом стартовые данные — туманы.

      Ваше же решение в любом случае будет работать за O(N * N), что гораздо дольше.

      Да. я там вообще много «косяков» наделал. Начиная с того, что бегал одним блоком по массиву данных. Здесь вариант просеивания гораздо эффективней, чем был раньше. Но хоть в прошлый раз, хоть в этот, я дошел до решения своими размышлениями. И если бы было бы чуть больше информации объеме данных, я думаю, задачку бы сделал иначе.

      • MichaelBorisov
        /#23148724

        вы дали ограничение по скорости и по памяти, но не сказали объем данных

        Почему вы с таким упорством отрицаете O-нотацию? Вам уже десятки людей на неё указали, даже авторы задачи.

        Там, где условие задачи неполное — надо его самостоятельно дополнять. Что мы знаем из условия? Что «Озон» хочет реализовать это решение для базы своих пользователей. Много ли пользователей у «Озона»? Наверное много, это большая фирма. Настолько ли много, что вся база не помещается в ОЗУ? Это вряд ли, так как такие задачи редко дают в качестве тестовых. В тестовых заданиях обычно идёт упор на академические знания.

        А академические знания — это асимптотика и O-нотация.

        И вот, в чём заключается её сила. Если алгоритмы O(n) могут отличаться друг от друга по скорости в разы или даже десятки раз — то O(n) от O(n^2) будет при больших n отличаться в тысячи, миллионы и миллиарды раз. Например, если при некотором большом n разные алгоритмы со сложностью O(n) выполняются 1, 5 и 10 минут каждый, то очень вероятно, что даже вылизанный и оптимизированный O(n^2) алгоритм будет работать неделями или месяцами. Здесь огромная разница, и «копейки» можно не считать.

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

        • RussianDragon
          /#23148776

          Там, где условие задачи неполное — надо его самостоятельно дополнять. Что мы знаем из условия? Что «Озон» хочет реализовать это решение для базы своих пользователей. Много ли пользователей у «Озона»? Наверное много, это большая фирма. Настолько ли много, что вся база не помещается в ОЗУ? Это вряд ли, так как такие задачи редко дают в качестве тестовых. В тестовых заданиях обычно идёт упор на академические знания.

          Там есть ограничение 256 мегабайт. т.е. 268 435 456 — байт… В int 4 байта, т.е. мы получаем число 67 108 864 пользователей забивают всю память.
          67 108 864 — Это много или мало? И это я не учитываю еще «накладные расходы» C#…

          А дальше мне начинают утверждать, что из задачи «предельно ясно», что нам нужна «древовидная структура» которая хранит «сколько там» еще ссылок… Ну допустим у каждого элемента по два предка. Т.е. так как минимум нужно хранить сам объект и две ссылки — 67 108 864 / 3. Ой уже 22 369 621… А нам еще нужно выполнять операции на этой структуре данных, да еще и за две секунды… Причем мы не знаем, порядок и частоту операций. Какая операция чаще проходит, какая нет. Может нам стоит использовать какой промежуточный кеш? Или вы конкретную хотите увидеть реализацию, тогда нужно говорить — сделайте «как мы хотим», но как хотим — не скажем. Т.е. от авторов решений просят тыкнуть пальцем в небо — может и угадают, что хотят авторы задачи.

          А говорить — «наиболее оригинальное» решение — а кто оценивает оригинальность и по каким критериям? Быстродейственноть, количество строк кода, знание нетривиальных конструкций языка?

          Где тут хоть какая-то ясность об условиях функционирования и оценки?

          • wataru
            /#23148814 / +2

            Вообще, если структуру хранить в массиве (дерево отрезков), то не надо никаких ссылок. Просто 2n ячеек для n элементов. У i-ой ячейки дети 2*i и 2*i+1. А если учесть, что тут еще можно и битовыми значениями обойтись, то достаточно 2n/8 байт памяти. Уже 1 миллиард какбы влезает. Понятно, что надо еще память на код, стек и все подряд выделить, так что по факту всего 512 миллионов пользователей можно легко в такой структуре поддерживать.


            А если разменять время работы на память, то можно использовать дерево Фенвика и там надо ровно n битов для хранения n элементов. И работать будет всего-то в пару раз медленнее. Уже миллиард влез.


            И все операции добавления и проверки за O(log n).

            • RussianDragon
              /#23148846

              Признаю «прикольность» идеи.
              Но есть нюанс, что мы не знаем до какой степени авторы хотят, чтобы участники оптимизированы своё решение. Ибо мы эти задачи решаем в «свободное время», да и в целом не всегда такие извращения нужны. Но идея класс, это я признаю.)

      • gektor2510
        /#23150434

        @RussianDragon, в нашем случае нужна была структура, которая постоянно отвечает на запросы за наилучшую асимптотику. Поэтому количество данных неважно. Мы всегда готовы ответить на дополнительные вопросы и прояснить условия. В следующий раз, если вам что-то будет непонятно, напишите нам. Победителем этого конкурса стал участник, который предложил оптимальное и самое оригинальное решение и продумал все нюансы.   

    • RussianDragon
      /#23149140

      gektor2510, я тут понял, что Вам вообще MEX не уперся по своей сути согласно постановки задачи.
      Еще раз, Вы хотите:

      1) Зарегистрировать нового пользователя,
      2) Защифровать все текущие данные с помощью нового ключа x

      Тогда вот вам код, который будет выполнять вашу задачу.

      class Item
          {
              public uint Id { get; set; }
              public Item Next { get; set; }
          }
      
          class Program
          {
              static Item First { get; set; }
              static Item Last { get; set; }
              static uint CountUsers { get; set; } = 0;
              static uint AcumHash { get; set; } = 0;
              static void Main(string[] args)
              {
                  while (true)
                  {
                      Console.WriteLine("Выбирите действие");
                      Console.WriteLine("1 - Добавить новго пользователя");
                      Console.WriteLine("2 - Зашифровать данные");
                      Console.WriteLine("3 - выйти");
                      string comand = Console.ReadLine();
                      switch (comand)
                      {
                          case "1":
                              AddUser();
                              break;
                          case "2":
                              while (true)
                              {
                                  try
                                  {
                                      Console.WriteLine("Введите ключ (неотрицательное число)");
                                      uint key = uint.Parse(Console.ReadLine());
                                      HashingUsers(key);
                                      break;
                                  }
                                  catch (Exception)
                                  {
                                     Console.WriteLine("Ошибка ввода");
                                  }
                              }
                              break;
                          case "3":
                              return;
                          default:
                              Console.WriteLine("Ошибка ввода");
                              break;
                      }
                      PrintUsers();
                  }
              }
      
              private static void AddUser()
              {
                  var newItem = new Item()
                  {
                      Id = (CountUsers ^ AcumHash)
                  };
                  CountUsers++;
                  if (First == null)
                  {
                      Last = First = newItem;
                      return;
                  }
                  Last = Last.Next = newItem;
              }
      
              private static void HashingUsers(uint hash)
              {
                  AcumHash ^= hash;
                  var link = First;
                  while (link != null)
                  {
                      link.Id ^= hash;
                      link = link.Next;
                  }
              }
      
              private static void PrintUsers()
              {
                  var link = First;
                  while (link != null)
                  {
                      Console.Write($"{link.Id}, ");
                      link = link.Next;
                  }
                  Console.WriteLine();
              }
          }


      Мы вставляем записи с 0 в односвязный список O(1).
      Мы производим шифрование данных O(n)
      Задача решена с минимум памяти (Без оптимизации на двоичном уровне.)
      Искать MEX вообще не нужно, т.к. благодаря тому, что мы храним аккумулированный хеш, каждая новая вставка будет уже с учетом того, что подобного индекса точно нет в базе (а именно этого вы и пытаетесь добиться). Выйти за пределы uint мы тоже не можем, т.к. операции битовые.

      Всё — задача решена. И зачем вы столько времени посветили описанию MEX, если вам нужно просто вставить значение в базу с уникальным ключом?

      lair, wataru, MichaelBorisov или хотите сказать, что я опять неправильно понял задачу?

      • lair
        /#23149560

        Да, вы опять неправильно поняли задачу. В задаче прямым текстом написано: новые пользователи получают минимальный id из возможных.

        • RussianDragon
          /#23149602

          А зачем? Если мы так имеем разбросанные id-шники, то зачем нам при вставке нового пользователя брать минимальный? Более того, взятие минимального id — это в примере, а не в условии. В условии — взять id которого нет в базе.
          — Говорю — авторы сами намудрили решением простой задачи, а потом попросили пользователей тыкнуть пальцем в небо и написать решение которое будет похоже на их мудрёное, которое не отражает суть изначально поставленной задачи.

          • lair
            /#23149610

            А зачем?

            По условиям задачи. Это задача на алгоритмы и структуры данных, там "зачем" не всегда применимо.


            (хотя я могу придумать как минимум вариант "замедление роста длины идентификатора").


            Если бы нужно было только уникальные идентификаторы, давно есть UUID.


            Более того, взятие минимального id — это в примере, а не в условии. В условии — взять id которого нет в базе.

            Это неправда.


            • RussianDragon
              /#23149630

              Ладно, признаю. Натянули они Сову на глобус в условиях задачи. )
              Да и фиг с ними.)

      • gektor2510
        /#23150446

        @RussianDragon, вы были бы правы, если бы по условиям задачи не нужно было находить mex. Это было прописано. Плюс, как отметил @lair, есть и другие известные способы решения такой задачи

  14. nickolaym
    /#23148128

    Более общий алгоритм для мех:


    Исходные данные: массив неотрицательных чисел, повторения разрешены, длина N.
    Очевидно, что мех лежит в интервале [0;N].
    Отсюда очевидно, что числа >N можно просто выкинуть.


    Выполним сортировку-и-уникальность.


    Мы знаем, что все числа лежат в [0;N].
    Поэтому делаем так:
    Пусть голова массива a[0..k) уже упорядочена: a[i]=i
    Смотрим на a[k]=m.
    Если m>=N, то это число, которое надо проигнорировать. обменяем a[k] <-> a[N-1] и сократим массив: N--.
    Если k<m<N, то это число должно лежать в a[m];


    • если a[m]==m, то это копия, которую надо будет выкинуть: обменяем a[m] <-> a[N-1] и сократим массив: N--; будем повторять до тех пор, пока a[m] != m
    • обменяем a[k] <-> a[m]
      И будем так делать до тех пор, пока a[k] <= k.
      Если m==k, то это число на своём месте, идём дальше: k++.
      Если m<k, то это вакансия. То есть, k — MEX. Конец.

    Если мы дошли до конца, k==N, то k — MEX.


    Линейное время, константная память.

  15. shatsa
    /#23148522

    Автору поста рекомендую почитать про структуру данных BitTrie (Префиксное дерево).
    Используя эту структуру для хранения id-шников, можно реализовать функцию вставки нового пользователя со сложностью O(logN), а ключ шифрования хранить в отдельной переменной и обновлять его простым xor-ом, типа oldKey ^= newKey.

    • RussianDragon
      /#23148538

      Для хранения пользователей можно вообще односвязанный список использовать в контексте задачи. Так то вставка — O(1). Ключ шифрования вообще не нужно где-то хранить, о приходит как значение введенное в консоли и обновляет id записей.

      Задача вообще про другое, для меня это задача поиска MEX на несортированном множестве.

      Автору поста рекомендую почитать про структуру данных BitTrie (Префиксное дерево).

      В целом, всё имеет право на жизнь… По крайней мере я увидел, что задача от OZON сформирована так криво, что каждый решил её по-своему…
      Я здесь увидел только задачу поиска MEX на не сортированном массиве, кто-то решил, полностью поменять структурe данных. Кстати это не всегда возможно, если данных в базе излишне много. В общем и целом, хоть статью и заминуси, в первые в жизни для меня, это была интересная задачка и интересные мнения.

      • lair
        /#23148566 / +1

        Для хранения пользователей можно вообще односвязанный список использовать в контексте задачи. Так то вставка — O(1).

        O(N), потому что у вас вставка (по условиям задачи) должна возвращать новый идентификатор, а вы его находите за линейное время.


        Задача вообще про другое, для меня это задача поиска MEX на несортированном множестве.

        Вот в том-то и дело, что вы решаете задачу, которую решать не надо, а потом удивляетесь, что ваше решение не приняли. Выше уже есть ответ человека, ассоциированного с Озоном, который подтверждает мое мнение.

        • RussianDragon
          /#23148598

          O(N), потому что у вас вставка (по условиям задачи) должна возвращать новый идентификатор, а вы его находите за линейное время.

          Необязательно. Мне достаточно один раз «просеять» данные выкинуть всё, что является 1-цами и получить массив «свободных» чисел. И до следующей операции шифрования.
          А в случае «сортировки MEX» поиск каждого нового свободного числа будет быстрее, т.к. массив частично сохраняет отсортированную структуру. А если еще сохранить максимальное число после прохода и потом сравнивать его с длинной массива, то мы точно будем знать, что нужно брать вообще новое число, а не искать свободное.
          Эти варианты – не конечные с точки зрения оптимизации.

          Вот в том-то и дело, что вы решаете задачу, которую решать не надо, а потом удивляетесь, что ваше решение не приняли. Выше уже есть ответ человека, ассоциированного с Озоном, который подтверждает мое мнение.

          Да, уже прочел. Ну, уж как понял задачу, так и сделал.

          • lair
            /#23148634 / +1

            Необязательно. Мне достаточно один раз «просеять» данные выкинуть всё, что является 1-цами и получить массив «свободных» чисел.

            Ну вот вы и сделали свою структуру данных.


            Да, подумайте о ее эффективности (по памяти особенно) для случая, когда у вас есть два числа: 1 и int.Max-1.


            И до следующей операции шифрования.

            Вот в ней-то и проблема. Она не зря есть в условиях задачи. У вас может получиться, что операции идут подряд: вставка, шифрование, вставка, шифрование, и так далее. Оценивать алгоритм надо и для этого случая тоже.


            И не забывать для всех случаев еще и объем памяти оценивать.

            • RussianDragon
              /#23148704

              У вас может получиться, что операции идут подряд: вставка, шифрование, вставка, шифрование, и так далее.

              Вот непонятно как они идут. Задача сформулирована криво и очень размыто. Что чаще происходит — «шифрование» или «вставка». Или мы шифруем после каждой вставки. Или только вставки 1 000 000 записей решили «шифрануть».
              И от это всего будет зависит и структура данных и способ поиска. А говорить — «наиболее оригинальное» решение — а кто оценивает оригинальность и по каким критериям? Быстродейственноть, количество строк кода, знание нетривиальных конструкций языка?
              Без нормально ТЗ — результат ХЗ.

              При этом нет даже банальной возможности спросить или хоть каких-то автоматических тестов — которые сказали бы «что-то не так».

              И утверждать, что спустя три месяца после окончания конкурса чуть более подробную формулировку — это странно.
              В тексте задачи в основном описывалась, что такое MEX, на это делался огромный уклон. Т.е. фактически самое главное — быстро находить MEX… А задача «шифрования» и «вставки» просто второстепенные, что бы проверить как эффективно работает MEX «без историчности».

              • lair
                /#23148720 / +1

                Вот непонятно как они идут.

                Ну так надо оценить, какая последовательность как будет влиять.


                А то знаете ли, (некоторые) алгоритмы сортировки тоже зависят от того, какие данные на входе, но это не мешает их анализировать.


                В тексте задачи в основном описывалась, что такое MEX, на это делался огромный уклон. Т.е. фактически самое главное — быстро находить MEX… А задача «шифрования» и «вставки» просто второстепенные, что бы проверить как эффективно работает MEX «без историчности».

                Я боюсь, это вы себе додумали, что тут самое быстрое.

                • RussianDragon
                  /#23148794

                  Ну так надо оценить, какая последовательность как будет влиять.

                  А то знаете ли, (некоторые) алгоритмы сортировки тоже зависят от того, какие данные на входе, но это не мешает их анализировать.

                  Что-то я уже сбился о чем спор…
                  Я говорю, в рамках того, что через три месяца авторы дали чуть больше данных об условиях задачи — это не означает, что изначально задача сформулирована «понятным языком».
                  Собственно Вы сами говорите, что разные алгоритмы могут совершенно по разному работать в зависимости от условий. И тут я полностью согласен. Поэтому нужно описать условия в которых они будут проверяться.

                  А не говорить потом, что мы не в таких условия проверяли… И я не против сделать иное решение, если на то пошло. Я не доказываю, что мое решение — идеальное для всех случаев жизни. Более того я сам прекрасно понимаю, где и как его оптимизировать в зависимости от условий в которых оно будет.

                  • lair
                    /#23148842 / +1

                    Я говорю, в рамках того, что через три месяца авторы дали чуть больше данных об условиях задачи — это не означает, что изначально задача сформулирована «понятным языком».

                    Для вас она оказалась непонятной, да. Для кого-то другого, кто предложил префиксное дерево — оказалась более понятной. Так бывает.


                    Это все, тем не менее, скажем, не повод отрицать О-нотацию, как вы упорно делаете.