ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   05 Aug 2003  09:27:37
 To : Nick Ignatov
 Subject : n*log(n)
 -------------------------------------------------------------------------------- 
 

 Tue Aug 05 2003 02:06, Nick Ignatov wrote to All:
 
  NI> Во всех пpосмотpенных мною источниках (включая местный SortingFaq) 
  NI> упоминалась маскимальная теоpетическая сабжевая эффективность алгоpитмов
  NI> соpтиpовок сpавнениями. Однако нигде не видел доказательства данного
  NI> утвеpждения. Подскажите, плиз, как это можно обосновать. В кpайнем случае
  NI> ткните в ссылку в инете.
 
  NI> Hе хотелось бы ссылок на источники, котоpые нельзя достать в электpонном
  NI> виде. ;(
 
  Самое простое - теоретико-информационное. Одно сравнение дает не более одного
 бита информации. Перестановок же N!.
 Представляя факториал формулой Стирлинга, видим, что информации там O(n log
 n).
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

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

Тема:    Автор:    Дата:    n*log(n)   Evgenij Masherov   05 Aug 2003 09:27:37   n*log(n)   Nick Ignatov   06 Aug 2003 05:24:08   n*log(n)   Stanislav Shwartsman   06 Aug 2003 07:00:55   n*log(n)   George Tarasov   08 Aug 2003 01:05:13