Сублинейный алгоритм / найти последний из различных элементов

Question

Справочная информация на случай, если вам не все равно, если не пропустите ее:

Я записывал сегодня немного аудио для проекта, делая его абзацем за раз.Если я испортил абзац, я переделал его, пока не понял, а затем перешел к следующему абзацу.Когда я загрузил их на компьютер, мне нужно было найти последнюю запись для каждого абзаца.Без каких-либо сведений о количестве записей, которые я сделал для определенного абзаца, как мне это сделать?(Разве вам не нравится, когда алгоритмы пробираются в вашу повседневную жизнь?)

В терминах алгоритмов у вас есть массив элементов, где за каждым элементом следует другой элемент того же типа, илисовершенно другой элемент.Найдите каждый последний элемент последовательности (правильно записанный аудиоклип).

Проблема:

Итак, у вас есть массив объектов, где каждый элемент имеет поле idгде каждый идентификатор находится в следующем списке.Я хочу, чтобы объекты, которые являются последними из их идентификаторов, скажем, в массиве идентификаторов, например:

aabbbbbccddddddddddddddeefffffffffggghhhhiiiijjklmnnnnoo

Очевидно, что если длина строки равна n и имеется n различных элементов, это займет у вас nшаги, чтобы понять это.Меня больше интересует общий алгоритм.Я мог бы сделать это с помощью алгоритма типа бинарного поиска, но я не знаю время его выполнения в том случае, если не знал о входных данных, кроме количества общих элементов.

Кроме того, знал бы числоразные идентификаторы меняют время выполнения алгоритма?Это интересная проблема для меня, и я прошу удовлетворить только мое интеллектуальное любопытство.

Answer 1

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

Затем вы переходите к следующему элементу и повторяете двоичный поиск, где заканчивается эта id-последовательность.

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

Предполагая, что n / m (среднее число элементов для определенного идентификатора) больше, чем log n , вы получаете сублинейный алгоритм.

Если n / m меньше log n , вам лучше искать конец id-последовательности линейно.

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

Answer 2

Получить первый и последний элементы в массиве и проанализировать средний элемент в этом диапазоне.Если найден новый id, поместите последний элемент в стек (с id и его диапазоном найденных позиций).В противном случае продолжите бинарный поиск в диапазоне между самым низким и средним элементом.Когда найден один последний отдельный элемент, вытолкните стек и продолжите поиск.

Сложность времени равна O(m * log(n/m)), сложность пространства равна log(m).Где m - количество различных значений.

Answer 3

Вариант «классического» бинарного поиска состоит не в том, чтобы разбить все пространство, а в геометрическом росте.То есть, если вы находитесь в положении p , попробуйте посмотреть на p + 1, p + 3, p + 7, p + 15, ..., пока вы не найдете интервал, в котором происходит изменение нового идентификатора, и там вы можете либо разделить его с помощью классического бинарного поиска, либо даже снова начать новое увеличение в последний разизвестная хорошая позиция.

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

Answer 4

Бинарный поиск выполняется во времени, пропорциональном log (n). Это означает, что чем больше элементов вы добавляете, тем медленнее они растут. Точнее, экспоненциальный рост размера задачи означает линейный рост времени выполнения. Другими словами, каждый раз, когда вы удваиваете количество записей, вам нужно еще раз прослушать, чтобы найти то, что вы хотите.

Чтобы выполнить бинарный поиск, вы должны начать с середины списка записей и выяснить, нужна ли вам запись до или после нее, затем вы отбрасываете ту половину, которая не содержит ее. Если запись является правильным абзацем (но вы не знаете, хорошо это или плохо), сгруппируйте ее с последующим и отбросьте все записи перед этим. Продолжайте устранять половину (слушая среднюю), пока не уменьшите до 1 или 2 записей.