|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Antony Victoroff 2:5030/953.300 23 Jan 2002 18:20:49 To : Stanislav Shwartsman Subject : Re: Поиск ближайшей точки с координатами (x,y). --------------------------------------------------------------------------------
*** Ответ на сообщение из конференции FROM_ECHOES_TO_ME (Откарбоненная почта).
Приветствую Вас, Stanislav!
Ответ на письмо Stanislav Shwartsman к Antony Victoroff (Вторник Январь 22 2002
19:16)
SS>>> А просто измерить расстояние между заданной точкой и всеми
SS>>> точками массива O(N) уже не прокатит ?
AV>> это неинтересный подход. ненаучный :) и долгий. а если надо
AV>> постоянно
AV>> искать ближайших соседей ? :))
SS> А если не нужно постоянно ничего искать ?
SS> Посмотри начальное условие задачи !
AV>> тады можно использовать память O(N),
AV>> затратив время O(NlogN) на предобработку и потом искать
AV>> ближайшего
AV>> соседа за время всего-то O(logN). во как. опять же используя
SS> Уметь надо не воротить горы ненужных алгоритмов и наворотов, когда
SS> задача этого не требует. Или ты будешь утверждать, что O(N log N)
SS> круче, чем O(N) ? ;)))
я хочу сказать, что при массивных запросах (а в постановке задачи ничего не
сказано о том, массивные запросы или одиночные) гораздо эффективнее один раз
затратить время на предобработку O(NlogN), а потом уже искать пары за O(logN),
что эффективнее чем O(N).
С уважением, Антон.
/3000.
... [home:latonita@mail.ru] [work:latonita@star.spb.ru] [ICQ#13382973]
---
* Origin: 2:5030/3000 (2:5030/953.300)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор Архивное /ru.algorithms/45373c4ec710.html, оценка из 5, голосов 10
|