Обсуждение:Быстрая сортировка - История изменений

Андрей Шулаев в 20:40, 11 июня 2012

2012-06-11T20:40:14Z

Андрей Шулаев в 18:49, 27 мая 2012

2012-05-27T18:49:19Z

Sementry: Новая страница: «X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij} E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{…»

2011-06-15T21:03:29Z

Новая страница: «<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_{…»

Новая страница

<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_{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>

<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>

← Предыдущая		Версия 20:40, 11 июня 2012
Строка 7:		Строка 7:
	* ссыки поместить в список		* ссыки поместить в список
	--[[Участник:Андрей Шулаев\|Андрей Шулаев]] 22:49, 27 мая 2012 (GST)		--[[Участник:Андрей Шулаев\|Андрей Шулаев]] 22:49, 27 мая 2012 (GST)
		+
		+	* В псевдокоде, судя по пояснению внизу, сортируется A[l; r], тогда зачем элемент q сортируется в обоих рекурсивных вызовах? Так алгоритм вполне может и зациклиться. Сделать, чтобы sort сортировал A[l; r).
		+	* Там же разные отступы. Один уровень — два пробела, почему два уровня — шесть?
		+	* Зачем используется wikitex там, где он вообще не нужен, а только создаёт огромные пробелы?
		+	--[[Участник:Андрей Шулаев\|Андрей Шулаев]] 00:40, 12 июня 2012 (GST)

@@ Строка 1: / Строка 1: @@
-<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_{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>
+* <tex>log</tex> -> <tex>\log</tex>
+* баги в процедуре partition
-<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>
+* написать о разных способах выбора опорного элемента (первый, последний, медиана из трёх, случайный)