Я читаю некоторые тексты об алгоритмической сложности (и я планирую пройти курс алгоритмов позже), но я не понимаю следующее.
Скажем, мне нужно найти элемент в неупорядоченном списке, количество шагов, необходимых для его поиска, будет пропорционально количеству элементов в этом списке. Поиск его в списке из 10 элементов может занять 10 шагов, то же самое для списка из 100 000 элементов может занять 100 000 шагов. Таким образом, алгоритмическая сложность будет линейной, обозначаемой «O (n)».
Теперь этот text[1] говорит мне, что если бы я отсортировал список по какому-то свойству, скажем, номеру социального страхования, алгоритмическая сложность поиска элемента была бы уменьшена до O(log n), что намного быстрее, off курс. Теперь я вижу, что это происходит в случае B-дерева, но как это применимо к списку? Я неправильно понимаю текст, ведь английский не мой родной язык?
[1]http://msdn.microsoft.com/en-us/library/ms379571.aspx
