Блог

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

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

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

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

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

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