Обсуждение:Быстрая сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Новая страница: «<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex> <tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{…»)
 
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
−
<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex>
+
* отсутствуют пробелы перед скобками (и иногда лишние после скобок)
 +
* заменить дефисы на тире
 +
* <tex>log</tex> -> <tex>\log</tex>
 +
* баги в процедуре partition
 +
* написать о разных способах выбора опорного элемента (первый, последний, медиана из трёх, случайный)
 +
* странные рекуррентные оценки для худшего случая. Просто показать, что опроный элемент пожет сдвигаться к краю и размер подзадачи уменьшается на единицу. Привести сам худший случай.
 +
* ссыки поместить в список
 +
--[[Участник:Андрей Шулаев|Андрей Шулаев]] 22:49, 27 мая 2012 (GST)
  
−
<tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex>
+
* В псевдокоде, судя по пояснению внизу, сортируется A[l; r], тогда зачем элемент q сортируется в обоих рекурсивных вызовах? Так алгоритм вполне может и зациклиться. Сделать, чтобы sort сортировал A[l; r).
−
 
+
* Там же разные отступы. Один уровень — два пробела, почему два уровня — шесть?
−
<tex> E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \frac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k+1} < \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k} = \sum\limits_{i=1}^{n-1}O(\log n) = O(n \log n)</tex>
+
* Зачем используется wikitex там, где он вообще не нужен, а только создаёт огромные пробелы?
 +
--[[Участник:Андрей Шулаев|Андрей Шулаев]] 00:40, 12 июня 2012 (GST)

Текущая версия на 23:40, 11 июня 2012

  • отсутствуют пробелы перед скобками (и иногда лишние после скобок)
  • заменить дефисы на тире
  • [math]log[/math] -> [math]\log[/math]
  • баги в процедуре partition
  • написать о разных способах выбора опорного элемента (первый, последний, медиана из трёх, случайный)
  • странные рекуррентные оценки для худшего случая. Просто показать, что опроный элемент пожет сдвигаться к краю и размер подзадачи уменьшается на единицу. Привести сам худший случай.
  • ссыки поместить в список

--Андрей Шулаев 22:49, 27 мая 2012 (GST)

  • В псевдокоде, судя по пояснению внизу, сортируется A[l; r], тогда зачем элемент q сортируется в обоих рекурсивных вызовах? Так алгоритм вполне может и зациклиться. Сделать, чтобы sort сортировал A[l; r).
  • Там же разные отступы. Один уровень — два пробела, почему два уровня — шесть?
  • Зачем используется wikitex там, где он вообще не нужен, а только создаёт огромные пробелы?

--Андрей Шулаев 00:40, 12 июня 2012 (GST)

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:Быстрая_сортировка&oldid=25064»