| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > BMsearch 2d |
| Автор: Crait 31.3.2004, 10:17 |
| Привет, уважаемые. Помогите, плиз, с реализацией, ну, или с алгоритмом быстрого поиска в двумерном (несортированном) массиве, работающего оптимальнее простого сравнения, вот как, например, поиск Бойера-Мура для строк. Пробовал придумать сам - уж очень наворочено получается. Кто-то тут, помнится, говорил, что для этих целей подходит двумерное преобразование Фурье. Можно подробнее ? |
| Автор: Abrek 1.4.2004, 15:00 |
| Я так понимаю, что нужно найти наперед заданное число в двумерном массиве (те его индексы i и j). Если так, то можно применить метод половинного деления. Делишь массив по одной из размерностей пополам и ищеш там число(перебором). Если находишь - хорошо, а не находишь - делишь пополам другую половину массива по другой размерности. И т.д. Работать будет в любом случае быстрее чем прямой перебор. Максимум в два раза, ну а минимум... зависит от размерности  |
| Автор: Crait 1.4.2004, 15:08 |
| Найти надо не число, а матрицу (меньшей размерности, чем массив, где осуществляется поиск). Второе. Массив НЕ СОРТИРОВАН. Так что метод половинного деления не катит  |
| Автор: maxim1000 1.4.2004, 15:34 |
| если никакой дополнительной информации об элементах нет, то никакие ухищрения не помогут. двумерное преобразование Фурье при вычислении использует значение функции в каждой точке, а значит уже будет вычислительно сложнее простого сравнения |
| Автор: Crait 1.4.2004, 18:14 |
| Ну почему же, при вычислении коррелляционных функций одномерных сигналов FFT позволяет очень заметно сэкономить на количестве операций (O(N*log(N)) вместо O(N*N)). |