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

Question

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

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

Под дублирующими элементами я подразумеваю элементы, которые встречаются в данном массиве более одного раза.

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

Как я вижу, должно быть 2n сравнений

for (int i=0; i<n; i++)
    if (a[i]==ele)
        break
    else
        continue;

Итак, в худшем случае два сравнения (i<n) и (a[i]==ele) были выполнены n раз. Поэтому 2n сравнений. Если есть какой-то способ, которым i<n может быть уменьшен, я не знаю, как.

Answer 4

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

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

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

Answer 5

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

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

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

Да, это все еще O (n).

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

Answer 6

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

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