@DimaMik

Добрый день!

Помогите, пожалуйста, с ответами на вопросы:

1) Какая асимптотическая сложность бинарного поиска в отсортированном двусвязном списке размера n?

а) О(log n)
б) О(n*log n)
в) О(n^2)
г) О(n)

2) Какая асимптотическая сложность бинарного поиска в отсортированном массиве размера n?

а) О(n)
б) О(log n)
в) О(n*log n)
г) О(n^2)

3) Какая асимптотическая сложность следующего алгоритма на псевдокоде. Дан массив array из n элементов (нумерация с 0 по n - 1):
integer my_mega_calc (integer[] array){
integer result = 0;
for (integer x = 0; x < n - 1; x = x + 1){
for (integer y + x; y > max(x - 1000, 0); y = y - 1){
result = result + array[y];
}
}
return result;
}

а) O(1)
б) O(n)
в) О(n^2)
г) О(n^1/5)
д) О(log n)

4) Какая средняя средняя асимптотическая сложность поиска в хеш-таблице (либо в ассоциативной хеш-таблицу), где n - кол-во элементов в таблице

а) O(1)
б) O(log n)
в) O(n)
г) О(n^2)

5) Какова временная сложность поиска в обычном массиве?

а) O(n)
б) O(1)
в) O(log(n))
г) O

0

@Arsegg

DimaMik, 1 - г, 2 - б, 3 - в, 4 - а, 5 - а.

2

@xoraxax

Насчёт хэштаблицы - я бы сказал о(logn)

0

@Arsegg

Ну это же не красно-черное дерево. Не нужно вводить в заблуждение.

0

@xoraxax

ну вот ты посмотри, что внутри хэшмапы например

0

@Arsegg

xoraxax, Хеш-таблица:

0

@xoraxax

так ты посмотрел, что внутри хэшмапы?

0

@Arsegg

0

@xoraxax

Так что будет представлять из себя хэшмапа, если у всех объектов будет одинаковый хэш?

0

@iSmokeJC

Насколько я помню, там от связного списка происходит переход к сбалансированному дереву. В восьмерке ввели, если не ошибаюсь.
И да, улучшается до logn в худшем случае

0

@xoraxax

Да не в худшем, а в среднем как раз. Коллизии, насколько я понимаю, не такое уж редкое явление.

0

@Arsegg

До Java 8 коллизии разрешались как раз через LinkedList. C Java 8 бакеты перестраиваются в RBT при числе static final int TREEIFY_THRESHOLD = 8; и более в бакете и общей емкости таблицы static final int MIN_TREEIFY_CAPACITY = 64; и более. При TREEIFY_THRESHOLD <= 6 RBT перестраивается обратно в LinkedList.
Т. е. вы хотите сказать, что при 6 элементах в бакете (в т. ч. одинаковый хеш), будет поиск выполняться в среднем за O(log(n))?

0

@xoraxax

причем тут 6 элементов?

0

@Arsegg

java.util.HashMap

0

@xoraxax

если меньше 6, то будет не дерево, а лист. Если больше 6 - будет дерево. Так вот если там дерево, то откуда там по-твоему o(1)?

0

@Arsegg

0

@Catstail

Arsegg, ох, боюсь вы меня немного переоцениваете... В конкретную реализацию нужно вникать. Я с ходу дать ответ не готов.

0