Оптимальный поиск в массиве |
Оптимальный поиск в массиве |
kosyak |
19.03.2010 17:04
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 100 Пол: Мужской Репутация: 0 |
Доброе всем время суток. Следующая задача: есть упорядоченный массив (например [1,6,7,9] ) и есть число N. Необходимо узнать первый элемент, который больше N. т.е. если N = 3, то первый элемент, больше N - 6. Какой алгоритм будет оптимальней для решения этой задачи?
|
Client |
19.03.2010 17:19
Сообщение
#2
|
Профи Группа: Пользователи Сообщений: 865 Пол: Мужской Реальное имя: Вячеслав Репутация: 20 |
в отсортированном массиве по-моему проще всего искать "быстрым поиском" (или как он называется, где выбирается каждый раз только половина диапазона)
|
Client |
19.03.2010 17:55
Сообщение
#3
|
Профи Группа: Пользователи Сообщений: 865 Пол: Мужской Реальное имя: Вячеслав Репутация: 20 |
если массив небольшой, то можно перебором, пока не найдешь нужный элемент
|
Lapp |
19.03.2010 18:45
Сообщение
#4
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
если массив небольшой, то можно перебором, пока не найдешь нужный элемент Client, а что значит в данном случае "небольшой"?P.S. Способ с делением пополам называется дихотомия. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
kosyak |
19.03.2010 18:47
Сообщение
#5
|
Пионер Группа: Пользователи Сообщений: 100 Пол: Мужской Репутация: 0 |
Ок, спасиба. Я тоже склонялся к бинарному поиску
|
Client |
19.03.2010 18:57
Сообщение
#6
|
Профи Группа: Пользователи Сообщений: 865 Пол: Мужской Реальное имя: Вячеслав Репутация: 20 |
это относительно я не знаю, есть ли ограничения на время выполнения или что другое. Массив из 100-200 элементов вполне можно и последовательно обработать
|
Lapp |
19.03.2010 19:52
Сообщение
#7
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
это относительно я не знаю, есть ли ограничения на время выполнения или что другое. Массив из 100-200 элементов вполне можно и последовательно обработать Относительно, но в меру. "Дважды два" - тоже относительно? Если автор спрашивает про алгоритм - я думаю, из этого уже следует, что его заботит время (а может, и место). Максимальное количество итераций в дихотомии есть Log2n, а в простом поиске равно n. Средние величины будем считать вдвое меньшими (хоть это и не совсем верно). И если отношение времен на одну итерацию при дихотомии и последовательном поиске равно k (один дихотомический шаг в k раз дольше последовательного), то для значения n, при котором дихотомия становится более выгодной, имеем уравнение: n = k*Log2n Разумным значением для k представляется примерно от 4 до 8 (зависит от способов адресации, типов сравниваемых величин..) Решить это уравнение можно простым перебором. Например, при k=8 получаем: n=16 левая часть: 16 правая часть: 32 n=32 левая часть: 32 правая часть: 40 n=64 левая часть: 64 правая часть: 48 Легко видеть, что решением является примерно n=50 (при желании можно уточнить). Вот тебе и ответ на этот вопрос )). Но: а. нужно помнить, что он получен для k=8, в конкретных случаях нужно использовать конкретные значения k; б. если важно место, то есть объем кода (что бывает довольно редко), то посик оптимума усложнится. И, наконец, если все важно только время, то можно реализовать оба алгоритма и переключаться между ними в зависимости от текущего значения n (если оно не постоянно). -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
kosyak |
19.03.2010 20:00
Сообщение
#8
|
Пионер Группа: Пользователи Сообщений: 100 Пол: Мужской Репутация: 0 |
Спасибо большое, я все понял))
|
Текстовая версия | 28.09.2024 23:06 |