Здравствуйте, Alexander Poluektov, Вы писали:
AP>Если речь о среднем количестве инверсий в перестановке из N элементов, то оно стремится к 1/e, а не 1/2.
К N/e, конечно же.
Re[7]: min_element в контейнере с известным наименьшем элеме
Число сравнений ключей в i-м просеивании не больше i-1, как минимум равно 1, и — предполагая, что все перестановки ключей равновероятны, — в среднем равно i/2.
AP>Что такое "Сравнение ключей в i-м просеивании"?
Это число сравнений сортируемых элементов, необходимых для того, чтобы найти позицию вставки i-го элемента в алгоритме простой сортировки вставками. Или число итераций, которое необходимо для нахождения позиции вставки (ибо в каждой итерации осуществляется ровно одно сравнение сортируемых элементов).
Вот, собственно, код (перевожу с Oberon на C):
for (int i = 1; i < N; ++i)
{
int j = i;
x = a[i];
while (j > 0 && x < a[j - 1])
{
a[j] = a[j - 1];
--j;
}
a[j] = x;
}
И на i-м шаге цикла for среднее число шагов цикла while будет равно i/2. Согласно выкладкам тов. Вирта.
Теперь сравните этот цикл while с Вашим, и сделайте выводы.
Люди! Люди, смотрите, я сошел с ума! Люди! Возлюбите друг друга! (вы чувствуете, какой бред?)
Re[6]: min_element в контейнере с известным наименьшем элеме
Здравствуйте, slava_phirsov, Вы писали:
_>Здравствуйте, uzhas, Вы писали:
U>>основная проблема с корректным определением вероятностного пространства _>Про "теорему о динозавре" см. выше.
она неправильно применена, хотя опять же не видно вероятностного пространства
U>>прицепились к какому-то мутному параметру d, который имеет слабое отношение к "среднему кол-ву сравнений в алгоритме"
_>Параметр d здесь, насколько я понимаю, есть просто-напросто длина последовательности. Короче, синоним для того, что по классике принято обозначать буквой N.
все намного сложнее:
К> Iterator last = find_if(begin,end, _1<treshold);
К> return (last!=end) ? last : min_element(begin,end);
....
где d = distance(begin,last)
если бы оперировали N, то цены бы не было всем этим выкладкам =)
_>Вообще же, откровенно говоря, все эти выкладки, приводимые авторами в ветке, меня несколько озадачили.
аналогично
Re[8]: min_element в контейнере с известным наименьшем элеме
Здравствуйте, slava_phirsov, Вы писали:
_>Вот, собственно, код (перевожу с Oberon на C):
_>
_>for (int i = 1; i < N; ++i)
_>{
_> int j = i;
_> x = a[i];
_> while (j > 0 && x < a[j - 1])
_> {
_> a[j] = a[j - 1];
_> --j;
_> }
_> a[j] = x;
_>}
_>
_>И на i-м шаге цикла for среднее число шагов цикла while будет равно i/2. Согласно выкладкам тов. Вирта. _>Теперь сравните этот цикл while с Вашим, и сделайте выводы.
Сравнил. Сделал выводы.
Что Вы нашли общего в этом цикле с min_element_bounded, мне понять тяжело.
На этом месте Николаса из множества "мы с Николой" предлагаю исключить: рассуждения Вирта, разумеется, описывают приведенную сортировку вставками, но не описывают min_element_bounded.
Рискну повториться в третий раз, но среднее количество "дополнительных" сравнений в min_element_bounded равно среднему количеству инверсий в перестановках из N элементов, т.е. N/e.
Оттрассируйте пару конкретных случаев, и Вы убедитесь, что количества сравнений в обоих алгоритмах описываются весьма разными формулами.
Re[5]: min_element в контейнере с известным наименьшем элеме
Здравствуйте, uzhas, Вы писали:
_>>"Мы, конечно, в академиях не учились", U>в этом треде, видимо, никто не соображает в вероятностях U>основная проблема с корректным определением вероятностного пространства U>прицепились к какому-то мутному параметру d, который имеет слабое отношение к "среднему кол-ву сравнений в алгоритме"
Вы бы просветили, а то конструктива в Ваших сообщениях в этом топике маловато.
Re[9]: min_element в контейнере с известным наименьшем элеме
AP>Сравнил. Сделал выводы. AP>Что Вы нашли общего в этом цикле с min_element_bounded, мне понять тяжело.
Ну да и ладно. Предлагаю прекратить дискуссию. Dixi.
AP>Оттрассируйте пару конкретных случаев, и Вы убедитесь, что количества сравнений в обоих алгоритмах описываются весьма разными формулами.
А в том-то все и дело, что оттрассировать пару конкретных случаев — недостаточно. Надо усреднить по всем случаям. На то оно и среднее число сравнений.
Люди! Люди, смотрите, я сошел с ума! Люди! Возлюбите друг друга! (вы чувствуете, какой бред?)
Re[10]: min_element в контейнере с известным наименьшем элем
Здравствуйте, slava_phirsov, Вы писали:
AP>>Оттрассируйте пару конкретных случаев, и Вы убедитесь, что количества сравнений в обоих алгоритмах описываются весьма разными формулами.
_>А в том-то все и дело, что оттрассировать пару конкретных случаев — недостаточно. Надо усреднить по всем случаям. На то оно и среднее число сравнений.
Несложно написать программу, которая это делает (std::next_permutation как основной инструмент).
У меня была, как proof-of-concept, но не сохранилась, новую писать лень.
Re[5]: min_element в контейнере с известным наименьшем элеме
Здравствуйте, Alexander Poluektov, Вы писали:
AP>Ошибка выделена. Среднее количество "доволнительных" (выделены в коде) сравнений равно среднему количеству инверсий в перестановке, т.е. N/e.
Грубо говоря, имеем среднее количество сравнений (N / e + N / 2) = чуть меньше N. Лучше, чем std::min_element. Но не сильно. Или нет?
Люди! Люди, смотрите, я сошел с ума! Люди! Возлюбите друг друга! (вы чувствуете, какой бред?)
Re[6]: min_element в контейнере с известным наименьшем элеме
Здравствуйте, slava_phirsov, Вы писали:
AP>>Ошибка выделена. Среднее количество "доволнительных" (выделены в коде) сравнений равно среднему количеству инверсий в перестановке, т.е. N/e.
_>Грубо говоря, имеем среднее количество сравнений (N / e + N / 2) = чуть меньше N. Лучше, чем std::min_element. Но не сильно. Или нет?
Зависит от природы распределения элементов в контейнере, на самом деле.
Может быть сильно лучше; почти также; и даже несколько хуже.
