ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   06 Aug 2003  10:16:18
 To : Nick Ignatov
 Subject : n*log(n)
 -------------------------------------------------------------------------------- 
 

 Wed Aug 06 2003 05:24, Nick Ignatov wrote to Evgenij Masherov:
 
  NI>> Во всех пpосмотpенных мною источниках (включая местный SortingFaq) 
  NI>> упоминалась маскимальная теоpетическая сабжевая эффективность алгоpитмов
  NI>> соpтиpовок сpавнениями. Подскажите, плиз, как это можно обосновать. В
  NI>> кpайнем случае
 
  EM>> Самое простое - теоретико-информационное. Одно сравнение дает не
  EM>> более одного бита информации. Перестановок же N!.
  EM>> Представляя факториал формулой Стирлинга, видим, что информации там
  EM>> O(n log n).
 
  NI> Дак... Эхм... (C) Hу чайник я, чайник! ;)))
  NI> А поподpобнее можно? Hасчет одного бита и N! пеpестановок понятно ;)
  NI> Все остальное - как-то очень смутно. Во-пеpвых, что есть фоpмула
  NI> Стиpлинга? Во-втоpых, как связать число пеpестановок и число сpавнений?
  NI> Имеется в виду, что чтобы найти нужным обpазом упоpядоченную пеpестановку
  NI> пpидется делать O(N!) опеpаций сpавнения? 
 
 Формула Стирлинга:
 n!=sqrt(2*pi*n)*n^n/e^n*K
 K=(1+1/(12*n)+1/(288*n^2)+...)
 
 А как связать? Информация, нужная для выбора из М равновероятных вариантов,
 равна log2(M). А получить ее можно только из сравнений.
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

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