тривиальный односвязный запрос сложности списка

Question

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

Answer 1

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

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

Answer 2

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

Answer 3

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

Answer 4

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