Самый эффективный способ найти положение (индексы) из m наименьших элементов в списке из n уникальных номеров без изменения списка

Question

Вот посмотрите на мою попытку решить это (алгоритм):

position := 1
i := 2
k=[]
FOR b = 1, b <= m, b++
    WHILE i <= n DO
        IF i in k
            THEN i++
        IF position in k
            THEN position++
        IF A[i] < A[position]
            THEN position := i
        i++
    RESET i := 2
    ADD position to k[]
    RESET position := 1

Теперь это работает, но сложность для этого была бы по крайней мере n ^ 4, и я хотел бы что-то лучше. Любая помощь будет принята с благодарностью. Спасибо!

Answer 1

Мне непонятно, почему вы думаете, что временная сложность вашего алгоритма равна O (n ⁴ ); основной l oop повторяется m раз, внутренний l oop повторяет O (n) раз, а тесты i in k и position in k в этом внутреннем l oop являются O (m), если реализованы как линейные search или O (log m), если реализовано как бинарный поиск. Это дает временную сложность O (m ² n) или O (mn log m) соответственно. Они оба лучше, чем O (n ⁴ ), потому что m ≤ n.

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

Длина приоритета всегда не более m + 1, поэтому, если вы используете heap в качестве очереди с приоритетами, затем операции вставки и удаления наибольшего занимают O (log m) времени. Это сделано для (n - m) элементов массива. Начальная стадия вставки m индексов в кучу, и финальная стадия опроса m элементов из кучи, занимает время O (m log m). Это делает общую временную сложность O (m log m + (n - m) log m), что упрощается до O (n log m).

Answer 2

Вы делаете максимальную кучу размером m из первых m индексов массива. При сравнении индексов для поддержания кучи сравните соответствующие элементы массива.

Затем для каждого другого индекса:

• Если он не меньше (по элементам), чем самый большой в max-heap откажитесь от него;
• В противном случае удалите самый большой индекс из max-heap и вставьте новый в.

На протяжении всего процесса max -heap всегда будет содержать индексы m самых маленьких элементов, которые мы видели. Общая сложность O (n * log m).

Теоретически, для больших m - O (n) - лучше составить массив всех индексов и просто использовать quickselect, снова сравнивая их по соответствующим элементов, но это хуже в худшем случае, и m обычно мало по сравнению с n, когда этот алгоритм необходим.