#list #algorithm #time-complexity #big-o
Вопрос:
Предположим, у меня есть несортированный список, такой как приведенный ниже:
[1, 2, 3, 1, 1, 5, 2, 1]
и я хочу вернуть количество минимальных элементов (в данном случае min = 1), которое равно 4.
Быстрое решение состоит в том, чтобы просто найти минимум, используя какую-либо встроенную min() функцию, а затем снова повторить список и сравнить значения, а затем подсчитать их. O(2n) время.
Но мне интересно, можно ли сделать это строго O(n) вовремя — сделать только один проход по списку. Есть ли способ сделать это?
Комментарии:
1. O(n) и O(2n) — это одно и то же.
Ответ №1:
Помните, что обозначение big-O говорит о том, как масштабируется среда выполнения, а не об абсолютной среде выполнения. В этом смысле алгоритм, который выполняет два прохода по массиву, каждый из которых занимает время O(n), также имеет время выполнения O(n) — время выполнения будет линейно масштабироваться по мере увеличения размера входных данных. Так что ваш двухпроходный алгоритм будет работать просто отлично.
Более строгое требование состоит в том, чтобы у вас был алгоритм с одним проходом, в котором вы можете видеть все элементы один раз. В этом случае вы можете сделать это, отслеживая наименьшее число, которое вы видели до сих пор, и все позиции, где вы его видели. Всякий раз, когда вы видите значение,
- если это значение больше, чем самое маленькое, которое вы видели, игнорируйте его;
- если это значение равно наименьшему из виденных вами, добавьте его в список позиций; и
- если это значение меньше самого маленького, которое вы видели, откажитесь от своего списка всех самых маленьких элементов (на самом деле они не были самыми маленькими) и сбросьте его до списка только текущей позиции.
Это также занимает время O(n), но делает это за один проход.