Алгоритмическая сложность: почему порядок снижает сложность до O (log n)

Question

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

Скажем, я должен искать элемент в неупорядоченном списке, количество шагов, которое необходимо сделать, чтобы найти его, будет пропорционально количеству элементов в этом списке. Поиск его в списке из 10 элементов может занять 10 шагов, то же самое для списка из 100000 элементов может занять 100000 шагов. Таким образом, алгоритмическая сложность будет линейной и будет обозначаться как O (n).

Теперь этот текст [1] говорит мне, что если бы я отсортировал список по какому-либо свойству, скажем, по номеру социального страхования, алгоритмическая сложность поиска предмета была бы уменьшена до O (log n), что очень много быстрее, конечно. Теперь я вижу, что это происходит в случае b-дерева, но как это относится к списку? Я неправильно понимаю текст, поскольку английский не является моим родным языком?

[1] http://msdn.microsoft.com/en-us/library/ms379571.aspx

Answer 1

Бинарный поиск, проверьте середину, если цель выше, она должна находиться справа, если меньше ее среднего числа и так далее. Каждый раз, когда вы делите список на две части, вы получаете O (log n)

Answer 2

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