тривиальный запрос сложности с одиночным соединением

Question

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

Answer 1

Приятно подумать, но это все еще не улучшает работу по поиску. Независимо от того, сколько указателей у вас есть в разных частях списка, вам все равно придется анализировать каждый элемент в списке. Тем не менее, вы можете - два потока искать каждую половину списка, делая операцию в два раза быстрее в теории.

Answer 2

Только в случае, если данные связанного списка отсортированы. В противном случае, как уже сказано в другом ответе.

Answer 3

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

Чтобы иметь отношение к сложностям с большими значениями, вам требуется более чем постоянное изменение коэффициента. Если, например, у вас был указатель на деление пополам каждой половины, и снова каждая половина этого и т. Д., Вы бы закончили логарифмическую сложность вместо линейной - и вы бы превратили свой «связанный список» в (уже хорошо известное) резьбовое дерево.

Answer 4

Это было бы, но асимптотически было бы все равно. Тем не менее, есть структура данных, которая использует эту идею, она называется списком пропуска. Список пропусков - это связанный список, в котором некоторые узлы имеют больше указателей, которые в каком-то смысле указывают на середину остального списка. Идея хорошо проиллюстрирована на this image. Эта структура обычно имеет логарифмическую вставку для поиска и удаления.