производительность: найти индекс максимального значения в обр (разрешено связывание)

Question

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

1. сканирование и поиск максимума, затем сканирование дважды, чтобы получить вектор индексов

2. сканирование и поискмаксимум, вдоль этого массива индексов конструкции сканирования и отбросить, если есть лучший.

Позвольте мне теперь, как я должен взвесить эти два подхода с точки зрения производительности (главным образом, сложность времени Iпредположим)?Мне трудно, потому что я даже не представляю, каков будет худший вариант для второго подхода!Это не сложная проблема perse.Но я просто хочу знать, как подойти к этой проблеме или как я должен решить эту проблему, чтобы получить ответ.

Answer 1

С точки зрения сложности:

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

Первое сканирование O(n).
Второе сканирование - O(n) + k вставок (с k, числом максимального значения) vector::push_back имеет амортизированную сложность O(1).таким образом, всего O(2 * n + k), который может быть упрощен до O(n) при сканировании k <= n

и нахождении максимума,
по этому массиву индексов конструкции сканирования и отмене, если лучше

Сканирование O(n).
Количество вставок сложнее вычислить.
Число clear (и количество очищенных элементов) также сложнее вычислить,(Сложность clear будет меньше или равна количеству удаленных элементов)

Но оба имеют верхнюю границу n, поэтому сложность меньше или равна O(3 * n) = O(n), но также больше, чем равнаO(n) (Сканирование), так что O(n) тоже.

Так что для обоих методов сложность одинакова: O(n).

Для производительности синхронизация ,Как всегда, вы должны измерить.

Answer 2

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

Однако я хотел бы добавить два пункта:

Во-первых, сравнение производительности может зависеть от компилятора, от того, как выполняется оптимизация.

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

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

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

Answer 3

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

Для второго метода реализация проще. Вы просто найдете Макс с первого раза. Затем вы найдете индексы, которые соответствуют на втором ходу.