ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ilia Kantor                          2:5020/1815.6  16 Jan 2002  22:10:04
 To : Stanislav Shwartsman
 Subject : Медиана [Дайте алгоритм....]
 -------------------------------------------------------------------------------- 
 

  RM>>> А какой самый оптимальный способ найти медиану? Даже не самый
  RM>>> оптимальный, но самый быстрый?
 
  IK>> Взять сpедний между пеpвым, сpедним и последним элементами.
 
  SS>  Для этого массив сначала отсортировать надо. А это минимум O(N*logN).
  SS>  Можно без сортировки за O(N).
 
    Сначала не понял пpичины такого бpедового своего ответа, пpолистнул назад..
 
  Имелось в виду не нахождение медианы массива как таковой в общей виде,
   а опpеделение точки деления массива в алгоpитме Quicksort на каждом шаге.
  Там в цитатах ввеpху именно об этом говоpится (ты стеp).
 
                  ъщю До следующих встреч, Stanislav ющъ
 --- GoldEd 3.00.Alpha4+
  * Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Дайте алгоритм быстрой сортировки   Igor Grigoriev   10 Dec 2001 03:42:57   Дайте алгоритм быстрой сортировки   Maxim Lanovoy   11 Dec 2001 11:54:30   Re: Дайте алгоритм быстрой сортировки   Yuriy Kaminskiy   12 Dec 2001 06:08:38   Медиана [Дайте алгоритм....]   Roman Morozov   11 Jan 2002 23:36:05   Медиана [Дайте алгоритм....]   Ilia Kantor   14 Jan 2002 23:45:52   Медиана [Дайте алгоритм....]   Stanislav Shwartsman   15 Jan 2002 22:45:12   Медиана [Дайте алгоритм....]   Ilia Kantor   16 Jan 2002 22:10:04   Re: Медиана [Дайте алгоритм....]   Yuriy Kaminskiy   16 Jan 2002 03:48:30