Поиск неотсортированного массива

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

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

Каким будет наименьшее и наибольшее количество сравнений в несортированном массиве. в котором могут быть и дублирующиеся элементы?

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

Я понимаю, что найти что-либо в несортированном массиве является проблемой O(n). Но верно ли верно ли это, если массив содержит дублирующиеся

Да, это по-прежнему O(n).

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

Идея в том, что вам нужно пройти по массиву от начала до конца, потому что он не отсортирован. Это означает, что вы смотрите на O (n) - линейный обход элементов.Независимо от того, находится ли тот, который вы ищете, в позиции 0, позиции 8 или позиции n-1, вам нужно пройти по массиву, чтобы найти его.

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

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

Худший случай - для данного значения нет дубликатов, и это последнее значение, которое вы проверяете - n-е сравнение.

Если вам нужно найти ВСЕ дубликаты, всегда будет n сравнений, потому что вам нужно будет посетить каждый элемент в несортированном массиве.

Время O(n) верно, даже если есть дублирующиеся элементы. Вам следует ознакомиться с big-oh нотацией.

В худшем случае рассмотрим такой массив: 1, 1, 1, 1, ..., 1, 1, 2. Для поиска 2 потребуется ровно n сравнений, если начинать с первого элемента, так что наличие дубликатов совсем не поможет. Если бы вы искали 1, то нашли бы его за одно сравнение, но есть входы отдельных элементов, для которых вы также сможете найти элемент за одно сравнение, если вам повезет, так что наличие дубликатов мало что значит, кроме того, что вам скорее всего повезет и вы найдете целевой элемент за меньшее количество шагов. Однако это все равно будет O(n).

Почти всегда есть лучшие и худшие случаи. Практическая производительность большинства алгоритмов всегда зависит от заданных входных данных, а обозначение big-oh лишь дает вам смутное представление о том, как будет работать алгоритм. Это не значит, что асимптотические обозначения бесполезны, просто они не всегда полностью точны, потому что есть базовые константы, которые имеют значение на практике.

Если вы сомневаетесь в производительности, проведите собственные сравнительные тесты.