Отправлено bialix 05 июня 2003 г. 13:51 В ответ на: Ответ: отправлено Mik 05 июня 2003 г. 13:43

Пока здесь все это обсуждаем у меня в голове сформировалось такое решение - поиск с прореживанием. Т.е. разбить рабочий диапазон на ряд поддиапазонов. Имеем точки - границы диапазонов. Находим в какой диапазон мы попали. Далее ищем внутри этого диапазона. Каждый диапазон можно еще разбить на ряд поддиапазонов. Поскольку каждое сравнение для float-чисел это операция вычитания, то можно примерно прикинуть время поиска по таблице для худшего случая

• Я, наверное, чего-то не понимаю. — John   (05.06.2003 15:01, 435 байт)
  • Вы все правильно понимаете — bialix   (05.06.2003 15:12, 297 байт)
• Может тогда уж просто двоичный поиск? Зачем изобретать велосипед? — Mik   (05.06.2003 13:59, пустое)
  • Ответ: Насколько я знаю двоичный поиск применим только в упорядоченных таблицах, или нет? — Bill   (05.06.2003 14:37, пустое)
    • однозначно. — DASM   (05.06.2003 14:53, пустое)
    • в смысле, чтобы значения шли по возрастанию? — bialix   (05.06.2003 14:42, пустое)
      • Ответ: Неважно, по возрастанию или по убыванию все равно. Главное - чтобы таблица была отсортирована. — Bill   (05.06.2003 15:51, 65 байт)
  • может подскажете, какое время поиска по двоичному алгоритму для худшего случая, если помните, конечно? — bialix   (05.06.2003 14:04, пустое)
    • А что тут помнить, и так очевидно: LOG(N). — Mik   (05.06.2003 14:12, пустое)
      • для таблицы в 300 значений это будет 8-9 сравнений. Гм. кхе-кхе. ха! И чего я сразу на бинарный поиск там плохо говорил? — bialix   (05.06.2003 14:19, пустое)
        • только не забудьте - на написание первой в мире ПРАВИЛЬНОЙ программы двоичного поиска ушло около 15 лет (кажись в 60-х годах писали) — DASM   (05.06.2003 14:36, пустое)
          • Жаль что Билли не догадался Винду в машинных кодах писать — Владимир З   (05.06.2003 17:35, пустое)
          • а сколько потратили на вторую программу? может тут тоже закон Мура применим? — bialix   (05.06.2003 14:45, пустое)
            • незнаю (+) — DASM   (05.06.2003 14:50, 74 байт)
              • а кто автор книги? — bialix   (05.06.2003 15:00, пустое)
                • Ответ: — DASM   (05.06.2003 15:03, пустое, ссылка)
        • а потенциально можно уменьшить время поиска — bialix   (05.06.2003 14:27, 144 байт)
          • Ответ: — Mik   (05.06.2003 14:48, 623 байт)
            • знаете, я из такого "спортивного" интереса — bialix   (05.06.2003 14:58, 466 байт)