Поиск элемента по его значению за O(log(n))

@misterzx · Регистрация: 18.07.2015

Студворк — интернет-сервис помощи студентам

Какие из следующих стандартных контейнеров позволяют найти в них элемент по его значению за O(log(n))? поясните свой выбор

Java
1
2
3
4
5
    java.util.Vector<E> 
    java.util.ArrayList<E> 
    java.util.LinkedList<E> 
    java.util.TreeSet<E> 
    java.util.HashSet<E>

сортированный java.util.Vector<E>
сортированный java.util.ArrayList<E>
сортированный java.util.LinkedList<E>

@KEKCoGEN · 18.07.2015, 17:00

misterzx, а вы как думаете?

@misterzx · 18.07.2015, 17:23 **[ТС]**

Сообщение от KEKCoGEN

misterzx, а вы как думаете?

я думаю что это только hashset, кажется что он очень быстро ищет но пояснить не могу

@KEKCoGEN · 18.07.2015, 18:59

Сообщение от misterzx

кажется что он очень быстро ищет но пояснить не могу

для этого надо понять каким образом он ищет и как он устроен внутри.

@misterzx · 18.07.2015, 20:26 **[ТС]**

Сообщение от KEKCoGEN

для этого надо понять каким образом он ищет и как он устроен внутри.

подскажите где такое работает, я знаю как устроен arrayList и LinkedList, как он ищет внутри, но не знаю ищет он там за O(log(n))

@KEKCoGEN · 18.07.2015, 20:37

misterzx, если вы знаете как ищет внутри LinkedList, то должны знать что он делает это путем обхода каждого элемента списка. То есть O(n)
В arrayList если известен индекс элемента, то его поиск занимает константное время т.к происходит доступ к ячейке массива тоесть за О(1)
Про остальные коллекции легко можно найти в гугле

@misterzx · 19.07.2015, 07:57 **[ТС]**

в итоге arraylist не подходит поиск любого элемента не зависит от размера, и он не подходит для этого

Добавлено через 29 минут

Сообщение от KEKCoGEN

misterzx, если вы знаете как ищет внутри LinkedList, то должны знать что он делает это путем обхода каждого элемента списка. То есть O(n)
В arrayList если известен индекс элемента, то его поиск занимает константное время т.к происходит доступ к ячейке массива тоесть за О(1)
Про остальные коллекции легко можно найти в гугле
Последний раз редактировалось KEKCoGEN; Вчера в 20:39.

А как работает TreeSet, К примеру я знаю что arraylist основан на массиве а LinkedList основан на линках, а вот как совершается поиск по TreeSet ?

@KEKCoGEN · 19.07.2015, 08:51

Сообщение от misterzx

а вот как совершается поиск по TreeSet

он работает на основе черно-красного дерева.

@Геомеханик · 20.07.2015, 02:49

Java
1
2
3
4
5
6
7
8
9
10
//rb-tree сбалансированное, так что за O(log(n))
java.util.TreeSet
 
//в лучшем без цепочек за O(1), в худшем по цепочкам O(n)
java.util.HashSet<E> 
 
//остальные все за линейное время O(n)
java.util.Vector<E> 
java.util.ArrayList<E> 
java.util.LinkedList<E>

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

@KEKCoGEN 2399 / 2224 / 565 Регистрация: 28.12.2010 Сообщений: 8,672
	18.07.2015, 17:00
	misterzx, а вы как думаете? 0

@KEKCoGEN 2399 / 2224 / 565 Регистрация: 28.12.2010 Сообщений: 8,672
	18.07.2015, 20:37
	misterzx, если вы знаете как ищет внутри LinkedList, то должны знать что он делает это путем обхода каждого элемента списка. То есть O(n) В arrayList если известен индекс элемента, то его поиск занимает константное время т.к происходит доступ к ячейке массива тоесть за О(1) Про остальные коллекции легко можно найти в гугле 0