| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
алгоритм поиска элемента в массиве
Piero © (2005-11-30 12:55:00)Подскажите алгоритм поиска элемента в массиве,
массив очень большой (>10000 элементов), я так помню, что алгоритм дерева, дает наилучшие результаты. Спасибо
Piero (2005-11-30 14:36:00) [1]ладно, не надо, ничего писать я уже придумал
Anatoly Podgoretsky (2005-11-30 14:32:00) [2]Piero (30.11.05 12:55) я так помню, что алгоритм дерева, дает наилучшие результаты.
Неправильно понимаешь, дерево может быть вырожденым, тогда время поиска равно N
Двоичный поиск в дает время Log N
Piero (2005-11-30 14:30:00) [3]просто его написать нужно аккуратно, если нет такого элемента, то найти, те элементы между кот и должно находиться искомое значение, если есть готовое, напишите
Piero (2005-11-30 14:26:00) [4]Массив отсортирован, а вот насчет бинарного поиска это верно, если есть готовый напишите
Глупые Вопросы (2005-11-30 14:08:00) [5]Все алгоритмы поиска, насколько я понимаю, делаются в отсортированном массиве. В принципе можешь сделать и сортировку деревом, здесь тебе поможет, например, книга Вирта "Алгоритмы + структуры данных=программы".
Но это большой гемор. Проще в уже отсортированном массиве использовать дихотомический поиск (массив делится пополам, смотриться в какой из половин массива находится требуемое значение и так далее поеа не найдём).
Вообще, наверное есть уже готовые структуры, которые всё вышеописанное делают, как например STL в Visual C++
MBo (2005-11-30 14:08:00) [6]Для нахождения лучшего решения в конкретном случае - читать книжки по алгоритмам.
Общий случай - массив отсортировать, и использовать бинарный поиск.
| |
