Нет, указанный мною метод - это не метод пузырька. Например, последовательность 3, 2, 1 метод пузырька упорядочивает двумя проходами за три перестановки:
Хочу упорядочить конечную последовательность чисел за минимальное число шагов, просто меняя местами два числа на каждом шаге. Как это сделать?
Оказалось, что довольно просто. Находим минимальное число и переставляем его (если оно не на первом месте) с числом, находящемся на первом месте. То же самое делаем со вторым по величине числом и вторым местом, и т.д. до конца. Понятно, что это не обязательно оптимальный метод сортировки, поскольку нахождение числа нужной величины не бесплатно. Но для нашей цели это неважно, а важно, сколько раз приходится переставлять.
Доказать это строго я не могу, я проверил это статистически. Небольшое сомнение лишь в том, что последовательности у меня не совсем случайные, вдруг на совсем уж случайных это не так.
Аригинальный алгоритм - вычисляет сперва порядок, не переставляя ничего (!), а потом уже переставляет число, на заранее подготовленные позиции.
Аригинальный алгоритм - вычисляет сперва порядок, не переставляя ничего (!), а потом уже переставляет число, на заранее подготовленные позиции.
Это не алгоритм сортировки. Это алгоритм подсчета нужного числа перестановок. Более того, при его реализации сначала создается упорядоченная (!) копия исходной последовательности - упорядоченная все равно каким способом, которая и используется для подсчета.
Да все едино... Румын, болгарин
Зато бегать по всему массиву каждый раз не надо
O(n2) и там и там
А что, наверное, несмотря на
всё это давно пропахано, найдено лучших/эффективнейших способов и ухнуто в программные пакеты для компов
там не осталось места для очередных оптимизаций? НЕ ВЕРЮ: ибо тогда бесконечности всякие если хоть где-то хоть как-то теряюют смысл, то по всеобщей аналогии ОНИ (бесконечности) везде не нужны (на мой примитивный инфолиовзгляд). Например:
1.если вопрос только в том, чтобы "работал однопроходной алгоритм", то наверняка есть решение, заключающееся, в частности в том, что создается - примитивно столько массивов, сколько элементов и "работа проводится только с индексами"... Правда там сама КОМАНДА может быть сложнее "пузырьковых"...
2.А вообще-то если где-то кто-то (алгоритм ли) получал какой-то массив, то уже тогда он мог считать=индексировать элементы массива сразу в требуемом порядке .
3. В перспективе будет так: Как начальник скажет- так и придется сортировать... И это будет правильно! (Пример такой:
Warning: Spoiler![ Click to expand ][ Click to hide ]
брат, царства небесного, финансист в отставке трудился на директора рынка: аудит. Сказал что нечто НОВОЕ можно внедрить двояко: 1. фирме 20% прибыли, директору - 5%. 2. Фирме - в 2 раза меньше, директору - на 2% больше. Каждый с ТРЕХ раз отгадает что выбрал директор: где больше - себе)
там не осталось места для очередных оптимизаций? НЕ ВЕРЮ
В общем случае минимальная скорость алгоритма сортировки O(n*log(n))
Такая скорость достигнута, а значит верить или не верить бессмысленно.
Для специальных случаев скорость может быть еще улучшена, да.
там не осталось места для очередных оптимизаций? НЕ ВЕРЮ
В общем случае минимальная скорость алгоритма сортировки O(n*log(n))
Такая скорость достигнута, а значит верить или не верить бессмысленно.
Для специальных случаев скорость может быть еще улучшена, да.
О, спасибо за оперативный и точный ответ! Значит ученым (не мне) еще остается не паханое поле по всем трем направлениям:
1. Целочисленные вычисления оптимизаций (где иррациональным и трансцендентным нет места);
2. При создании массивов;
3. и при субъективном их применении Уверен, что большая часть всего, что
давно пропахано, найдено лучших/эффективнейших способов и ухнуто в программные пакеты для компов
сделано было удовольствия ДЛЯ и РАДИ оптимизации (и внутренней красоты) применения ПРОШЛЫХ мощностей СВТ... (типа процессора ОДНОразрядного ЭВМ ЕС). А сейчас, например, долго уговаривал коллегу-пенсионера, что ему ПО БАРАБАНУ отсутствие у него флэшки ТЕРРАБИТНОЙ... Ну не успею, как пенсионер, не только с пользой ее заполнить, а даже просмотреть все то, что там может быть, что целесообразно записать , а тем более потом прочитать, посмотреть, изучить, осознать, применить удовольствия ДЛЯ и истины РАДИ, при имеющемся самолюбии себя и окружающих. З павагай, паклонам
Есть две числовые последовательности одинаковой длины. Каждый член 1-й последовательности - это одно из 4 чисел, а каждый член 2-й последовательности - это одно из 7 чисел. Попарная сумма этих последовательностей, однако, принимает не 4х7 = 28 значений, а только 3 значения. Можно ли считать отсюда, что данные последовательности сильно связаны, при том что их коэфф. корреляции равен всего -0,173?
Есть две числовые последовательности одинаковой длины. Каждый член 1-й последовательности - это одно из 4 чисел, а каждый член 2-й последовательности - это одно из 7 чисел. Попарная сумма этих последовательностей, однако, принимает не 4х7 = 28 значений, а только 3 значения. Можно ли считать отсюда, что данные последовательности сильно связаны, при том что их коэфф. корреляции равен всего -0,173?
Пришлось поэкспериментировать. Взял - 1 000 000 раз - две чисто случайные последовательности той же длины (255). Члены первой последовательности принимали те же 4 значения (1, 2, 3, 4), но случайным образом, а члены второй - те же 7 значений (4, 5, 6, 7, 8, 9, 10), но тоже случайным образом. В итоге получилось, что их попарная, почленная сумма почти всегда принимает любое значение от минимального (1 + 4 = 5) до максимального (4 + 10 = 14) включительно и лишь изредка, в одном случае из 5000, она не принимает или минимального, или максимального значения.
Т.е. эта случайная сумма почти всегда принимает 10 значений и лишь изредка 9 значений. В исходной же задаче сумма принимает только 3 значения (8, 10, 12). Спрашивается, значимо ли это?
Т.е. эта случайная сумма почти всегда принимает 10 значений и лишь изредка 9 значений. В исходной же задаче сумма принимает только 3 значения (8, 10, 12). Спрашивается, значимо ли это?
Ничего пока не считал, но т.н. случайность - это непознанная закономерность позволяет утверждать что цитируемое и) значимо (наверняка в некоторой другой системе счисления, или при вычислении корреляции самих коэффициентов корреляции в 7-ричной или "натуральной" системе счисления) результат будет еще более впечатляющий... к) значимо не информационно-абстрактно, а классически (вычисления выполнены, если ошибки нет, то даже "отсутствие ожидаемого результата" - тоже результат). с) субъективно значимо.
Warning: Spoiler![ Click to expand ][ Click to hide ]
Точно помню, на втором курсе Гена Астапенко купил шарик воздушный с пищалкой и во время первого перерыва, вместо того чтобы курить сигарету, надувал шарик и пищал. На вопрос Паши Турайкевича (а зачем тебе это?) он спокойно ответил: если продают, значит
Есть две числовые последовательности одинаковой длины. Каждый член 1-й последовательности - это одно из 4 чисел, а каждый член 2-й последовательности - это одно из 7 чисел. Попарная сумма этих последовательностей, однако, принимает не 4х7 = 28 значений, а только 3 значения. Можно ли считать отсюда, что данные последовательности сильно связаны, при том что их коэфф. корреляции равен всего -0,173?
Пришлось поэкспериментировать. Взял - 1 000 000 раз - две чисто случайные последовательности той же длины (255). Члены первой последовательности принимали те же 4 значения (1, 2, 3, 4), но случайным образом, а члены второй - те же 7 значений (4, 5, 6, 7, 8, 9, 10), но тоже случайным образом. В итоге получилось, что их попарная, почленная сумма почти всегда принимает любое значение от минимального (1 + 4 = 5) до максимального (4 + 10 = 14) включительно и лишь изредка, в одном случае из 5000, она не принимает или минимального, или максимального значения.
Т.е. эта случайная сумма почти всегда принимает 10 значений и лишь изредка 9 значений. В исходной же задаче сумма принимает только 3 значения (8, 10, 12). Спрашивается, значимо ли это?
Я все-таки дожал эту задачу. Правда, пришлось более адекватно определить 1-ю последовательность, чтобы ее члены принимали еще и значение 0. Обозначим ее член через g, а член с тем же номером 2-й последовательности - через h. И тогда областью значений отношения (h - g)/(h + g) будет не что-нибудь, а ряд Фарея F5, всего 11 дробей.
Вот так и связаны исходные последовательности. Фишка не в том, что встречаются именно эти 11 дробей (они возникают и для случайных последовательностей), а в том, что никакие другие дроби не встречаются!
Дело было сто лет назад и не в моем универе, поэтому какие-то детали могли быть и другими, но все равно нет дыма без огня.
Лектор -- большой математик -- рассказывал студентам про так называемый гармонический ряд. Если кто забыл, это бесконечная сумма следующего вида : 1 + 1/2 + 1/3 + 1/4 + 1/5 .... и так далее. Профессор доказал на лекции, что этот ряд расходится, то есть, хотя каждое следующее слагаемое все меньше и меньше, сумма их рано или поздно превзойдет любое мыслимое число. Так вот, доказал он теорему, а потом мечтательно улыбнулся и говорит:
-- Представьте себе Байкал, из которого никакая Ангара не вытекает, и никакой Баргузин в него не впадает. Просто гигантское озеро с фиксированным объемом воды. А на берегу сидит Конфуций и пытается вычерпать Байкал наперстком. Причем не просто черпает каждый раз по наперстку, а уменьшает дозу: сначала целый наперсток, потом половинка, потом третья часть, потом четвертая... Так представляете -- рано или поздно он ведь его полностью вычерпает! Именно это мы с вами сейчас доказали.
А вид у него был мечтательный, повторю
The topic has been locked.
Математика для чайников №3
17 Март 2017 18:44 #616
Математика для чайников №3
20 Март 2017 12:02 #620
))
Я в свое время задавался этим вопросом для Ангары, вытекающей из Байкала.
Пусть современный сток (в истоке) Ангары 1850 м3/с постоянен, а объем Байкала 24 000 км3 не пополняется и вытекает до капли. Тогда для исчерпания потребуется
24000 х 109 / 1850 секунд ~ 400 лет.
А для Конфуция с гармонически убывающим наперстком сколько?
The topic has been locked.
Математика для чайников №3
20 Март 2017 13:28 #621
Не, Конфуцию никакого времени не хватит. Если считать, что объем наперстка, пусть первоначально равный 1 см3, гармонически убывает каждую секунду, а Конфуций работает со скорость 1 наперсток в секунду, то вычерпать 24 000 км3 воды ему потребуется примерно
е в степени (24000 х 1015), т.е. больше 1010 000 000 000 000 000 000, секунд,
тогда как возраст Вселенной для сравнения меньше 1018 секунд.
Математика для чайников №3
20 Март 2017 14:38 #622
))
Помните, конечно, в горбачевское время был проект переброски части стока северных рек в Каспийское море, поскольку его уровень катастрофически снизился. Но "общественность" этот проект успешно зарубила. Я тогда же задался вопросом: насколько повысится уровень Каспийского моря, если всю тогдашнюю общественность - максимум 290 млн человек - целиком утопить в этом самом море? Оцените, вы удивитесь.
The topic has been locked.
Математика для чайников №3
20 Март 2017 19:18 #623
инфолиократ
)) wrote:
Помните, конечно, в горбачевское время был проект переброски части стока северных рек в Каспийское море, поскольку его уровень катастрофически снизился. Но "общественность" этот проект успешно зарубила. Я тогда же задался вопросом: насколько повысится уровень Каспийского моря, если всю тогдашнюю общественность - максимум 290 млн человек - целиком утопить в этом самом море? Оцените, вы удивитесь.
До ВОСР в арифметических задачах "героями" были купцы, аршины и т.п.
Во времена СССР - пионеры, субботники и т.п.
После 2014 года стали основными героями НЕсогласные = "общественность" - здорово прилумали.
А все потому, что проигнорировали вселенсконатуральное....
The topic has been locked.
Математика для чайников №3
20 Март 2017 19:30 #624
инфолиократ
+ Учителю бывшего учителя, ЗА
ВТОРОЙ пример игнорирования вселенсконатурального:
-- Представьте себе Байкал, из которого никакая Ангара не вытекает, и никакой Баргузин в него не впадает. Просто гигантское озеро с фиксированным объемом воды. А на берегу сидит Конфуций и пытается вычерпать Байкал наперстком. Причем не просто черпает каждый раз по наперстку, а уменьшает дозу: сначала целый наперсток, потом половинка, потом третья часть, потом четвертая... Так представляете -- рано или поздно он ведь его полностью вычерпает! Именно это мы с вами сейчас доказали.
А вид у него был мечтательный, повторю
Quote Selected
Воронеж - це Європа!
...
Хайдук's Avatar
ув. инфолиократ вычерпанию Байкала не поверит
Last Edit: 17 Март 2017 18:44 by Хайдук.
onedrey's Avatar
Он просто не видел Конфуция
Этта математика хороша для проведения народных референдумов. Арифметика жизни предполагает, что Вселенсконатуральное это такое число, которое предполагает расположение ВСЕХ
абстрактных
объективных
субъективных дискретных (с точностью до 10 в минус 50й степени) единиц в одну прямую линию....
Короче, "посоветовавшись с Конфуцием- благодаря ГИ есть такая отдельная тема на КФ", отвечу вопросом на вопрос:
1.Разве Конфуций вычерпывал бы последню молекулу воды ДОЛЬШЕ, чем све озеро Байкал?
2.Разве Конфуций считал бы ВОДУ в количестве меньше молекулы ВОДОЙ?
3. кнс= каждый напишет свое(с), ув. самоед может легко подсчитать количество молекул воды...
З павагай к реалистам
The topic has been locked.
Математика для чайников №3
20 Март 2017 19:45 #625
Да, насчет молекул воды справедливое замечание. Тот "лектор - большой математик" считал, что вода непрерывна, а не дискретна, и не предусмотрел, что еще до исчерпания Байкала наперсток может уменьшиться настолько, что молекула воды просто в него не влезет и тогда Конфуций, работая впустую, не закончит свою работу НИКОГДА! Либо начальный наперсток должен быть достаточно объемным и, может быть, даже неподъемным для Конфуция. Надо бы проверить.
Один моль воды имеет объем 18 мл и содержит 6 на 1023 молекул воды. Значит, объем молекулы воды = 3 на 10-23 мл. Отсюда наперсток начальным объемом 1 мл уменьшится до объема молекулы воды за t = 1023/3 секунд, если Конфуций будет работать со скоростью 1 наперсток в секунду. И за это время он вычерпает ~ ln t мл воды, т.е. ~ 50 мл, смех.
The topic has been locked.
Математика для чайников №3
21 Март 2017 14:06 #628
Вот полезный совет, я сам им все время пользуюсь. При оценке чего-то по порядку величины удобно считать, что "год", все равно какой, 365 или 366 дней, довольно точно составляет 107.5 и даже 107.50 секунд.
The topic has been locked.
Математика для чайников №3
22 Март 2017 03:30 #629
Какие проблемы волнуют современных математиков? Какие требуют решения? В чем важность теоремы Пифагора, которую каждый из нас знает со школы, и почему она может быть фундаментом для нахождения общего языка в случае нашего возможного контакта с некоей инопланетной цивилизацией? Обо всем этом и о многом другом рассказывает Алексей Савватеев, доктор физико-математических наук, ректор Университета Дмитрия Пожарского, профессор МФТИ, ведущий научный сотрудник Центрального экономико-математического института РАН, популяризатор математики. Ролик подготовлен в рамках проекта «Ковчег идей» студией Sci-One TV.