1

Здравствуйте. В гугле не нашел почти никакой информации по этому поводу.

Скажите, за какое время можно найти элемент по его значению в Vector'e и ArrayList'e? Чем объясняется время поиска? Я почему-то думаю, что за О(n), т.к. все равно придется пробегаться по всем элементам, пока не найдем тот, который нужен. Но, с другой стороны, почему-то мне кажется, что за О(log(n))

Заранее спасибо

1
  • в отсортированном можно за log(n) с помощью бинарного поиска
    – pavel
    Commented 4 апр. 2016 в 12:15

1 ответ 1

4

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

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

Касаемо различий между поиском в ArrayList и Vector - разницы практически не будет, поскольку каждый из этих контейнеров предоставляет доступ к элементу по индексу, что критически важно для бинарного поиска.

0

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.