Как бы вы перешли связанный список в O (n ^ 0.5)?

Question

Это вопрос интервью Apple.Я не нашел убедительных аргументов в поддержку или против этого.

Answer 1

Обход более эффективен, чем O (n), невозможен, поскольку для "обхода" требуется доступ к каждому узлу по очереди .

Возможно сделать произвольный доступ быстрее, чем O (n), хотя, поддерживая второй связанный список, который сохраняет ссылки на промежуточные узлы; Затраты на вставку, удаление и добавление будут расти из-за усложнения ведения второго списка.

Answer 2

Не возможно.

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

Answer 3

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

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

Ознакомьтесь со статьей в Википедии дляАлгоритм Гровера здесь .

Они устанавливают амортизированное время работы O (n ^ 0,5) и пространство O (log n).Также следует отметить, что он не является детерминированным.Это означает, что существует высокая вероятность того, что алгоритм вернет правильный результат, но это не гарантировано.

Я предполагаю, что этого достаточно, чтобы передать вопрос, но остальное у меня над головой.

Удачи.

Answer 4

Возможно, если у каждого узла есть связь со следующим элементом, предыдущим элементом и центральным элементом (где центр - это средняя точка между текущим элементом и концом списка).

Мысли?