tag:blogger.com,1999:blog-9149260308162775442.post4905805852889193171..comments2023-11-06T20:57:53.318+03:00Comments on Алгоритмы на С++ (олимпиадный подход): Часть 1. Знак перестановки. Подсчет количества инверсийslipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-9149260308162775442.post-65464123537694249702012-06-30T21:08:36.902+04:002012-06-30T21:08:36.902+04:001. Выход на O(N) читайте в Кормене
2. Опять повтор...1. Выход на O(N) читайте в Кормене<br />2. Опять повторюсь, не нужно ждать чудес от карманой сортировки. Случай 316-317 и вправду работает долговато.slipstak2https://www.blogger.com/profile/15957109470497214310noreply@blogger.comtag:blogger.com,1999:blog-9149260308162775442.post-60713464758486207422012-06-30T09:43:10.225+04:002012-06-30T09:43:10.225+04:00И, кстати, при 316-317 работает всё те же 3 секунд...И, кстати, при 316-317 работает всё те же 3 секунды.Anonymoushttps://www.blogger.com/profile/17152157727140681943noreply@blogger.comtag:blogger.com,1999:blog-9149260308162775442.post-2937244567614462812012-06-29T23:41:04.689+04:002012-06-29T23:41:04.689+04:00Ага. Что-то начало проясняться. При C =~ M это не ...Ага. Что-то начало проясняться. При C =~ M это не квадрат, а O(2N*sqrt(N)). Но выхода на N всё равно не вижу.Anonymoushttps://www.blogger.com/profile/17152157727140681943noreply@blogger.comtag:blogger.com,1999:blog-9149260308162775442.post-66579481171786588292012-06-29T23:00:10.541+04:002012-06-29T23:00:10.541+04:00А кое-что запуталось, уже с точки зрения математик...А кое-что запуталось, уже с точки зрения математики. O(N*(C+M)) = O(N*(C+N/C)) = O(N*C+N*N/C) = O(N*N). Так? В каком месте надо применить хак с матоожиданием, чтобы в этой выкладке не перейти к O(N*N)?Anonymoushttps://www.blogger.com/profile/17152157727140681943noreply@blogger.comtag:blogger.com,1999:blog-9149260308162775442.post-15906788688387361832012-06-29T22:55:37.692+04:002012-06-29T22:55:37.692+04:00Собственно, именно академический интерес меня и ве...Собственно, именно академический интерес меня и ведёт, потому как деревья Фенвика - очевидно и самый красивый, и самый эффективный способ решения этой задачи.<br /><br />Большое спасибо за выкладки. Многое у меня в голове прояснилось.Anonymoushttps://www.blogger.com/profile/17152157727140681943noreply@blogger.comtag:blogger.com,1999:blog-9149260308162775442.post-28150118558822352902012-06-29T18:35:59.379+04:002012-06-29T18:35:59.379+04:00Карманная сортировка имеет скорее академический ин...Карманная сортировка имеет скорее академический интерес. Работает с очень большой константой и при условии равномерного распределения значений внутри сортируемого массива.<br /><br />Что касается выбора размера кармана(он же корзинка).<br />Тут следующие соображения:<br /><br />Рассмотрим предложенный Вами случаи для 100.000 элементов:<br />1) Количество карманов = 100; Размер кармана = 1000<br />В этом случае не надо сортировать карман квадратичной сортировкой. Лучше подойдет какая нибудь из "быстрых".<br />2) Количество карманов = 1000; Размер кармана = 100<br />Учитывая, что размер кармана не велик, то возможно лучше подойдет эффективная реализация квадратичной сортировки. Известно, что маленькие массивы лучше сортировать квадратичной сортировкой. Но как узнать границу, после которой массив перестает быть маленьким? По моим наблюдениям в общем случае эта верхняя граница находится между 32 и 40. У Тима Петерсона в Tim Sort'e это 64(правда это на Python'e). 100 - не такое большое число и возможно нет принципиальной разницы чем и как сортировать.<br /><br />3) Количество карманов = 317; Размер кармана = 316.<br />Вот тут самое интересное.<br />Пусть N - общее количество сортируемых элементов, M - количество карманов, С - количество элементов внутри кармана.<br />В данном коде: http://www.everfall.com/paste/id.php?oipol8yb4phq можно проследить, что общее время работы равно<br />O(N*(C+M)). Нужно минимизировать С+M, при этом M = N/C, т.е нужно минимизировать C+N/C.<br /><br />Короче говоря все свелось к классической школьной задаче: Нужно найти отношение сторон прямоугольника с фиксированной площадью, так чтобы его периметр был минимальным. Данное условие достигается, когда стороны относятся как 1:1. Так и в нашем случае С должно быть равно M.slipstak2https://www.blogger.com/profile/15957109470497214310noreply@blogger.comtag:blogger.com,1999:blog-9149260308162775442.post-5925598596140038752012-06-29T17:22:59.562+04:002012-06-29T17:22:59.562+04:00Хмм... Интересно.
Прочитал выкладки из Кормена, к...Хмм... Интересно.<br /><br />Прочитал выкладки из Кормена, которые, впрочем, полностью повторяют русскую Википедию, проникся.<br /><br />Собственно, вопрос у меня возник потому, что в моей реализации (Ruby) на 100 000 чисел сортировка слиянием считает количество инверсий за 0,75с. Фенвик за 0,5с. А корзинки, если их 1000 и в каждой 100 элементов - за 7 секунд. Если их 100 и в каждой 1000 - за 3 секунды. Посмотрел, кто тормозит в каждом конкретном случае, так во втором конкретно тормозил поиск точки вставки - если его заменить на рандом, алгоритм отрабатывал за полсекунды. То есть, тормозила не вставка, а именно поиск. А поскольку я использовал обычный рубишный массив, то я имею возможность сделать по нему бинарный поиск, что тоже резко ускоряет алгоритм.<br /><br />И вот с этого места мне стало казаться, что это не N.<br /><br />Что вы думаете по этому поводу? Я уже понял (хотя и не понял, почему, так что, скорее поверил), что лучший случай, когда размер корзинки равен количеству корзинок. А для 100 000 лучше 100 корзинок по 1000, 1000 корзинок по 100 или 316 корзинок по примерно 317?Anonymoushttps://www.blogger.com/profile/17152157727140681943noreply@blogger.comtag:blogger.com,1999:blog-9149260308162775442.post-56366876270456298432012-06-29T16:14:59.655+04:002012-06-29T16:14:59.655+04:001. По поводу подсчета количества инверсий с помощь...1. По поводу подсчета количества инверсий с помощью карманной сортировки.<br />Вы не спорите, что карманная сортировка работает за O(N). Давайте вспомним, что там происходит:<br /> a) Все элементы раскидываются по карманам.<br /> b) Каждый карман сортируется сортировкой вставками.<br />Фиксируем количество карманов(константа С). Размер кармана пропорционален N, то тогда получается по Вашим доводам сортировка кармана работает за O(N*N), т.к. п.b) будет работать именно с такой сложностью. Итого общее время работы С*O(N*N). В Кормене(второе издание с.230-234) описываются мат. выкладки, доказывающие линейность карманной сортировки.<br />Что касается инверсий, то по сути дела в приведенной реализации происходит карманная сортировка в online режиме и вся мат.часть из Кормена подходит и под этот случай.<br /><br />2. Не совсем понял конец фразы "В версии из видео можно сумму считать на дереве Фенвика, тогда получится O(log(N)) тело цикла и O(N*log(N)) итого. Но не более."<br /><br />3. Пробовать на 100.000 элементов я не стал.<br />Изначально задача формулировалась для 10.000 элементов, собственно поэтому и родилась идея попробовать все три метода. 100.000 элементов лучше решать Фенвиком.<br /><br />P.S: Напомню, что по условию задачи мы имеем дело с перестановкой, поэтому при использовании карманной сортировки все карманы забиваются равномерно. Идеально подходит случай, когда количество карманов равно количеству элементов внутри кармана. Т.е. случай когда количество карманов = sqrt(N). Для случая в 10.000 элементов размер кармана в 100 раз меньше размера всей коллекции, поэтому можно условно считать, что сортировка кармана выполняется за большую константу.slipstak2https://www.blogger.com/profile/15957109470497214310noreply@blogger.comtag:blogger.com,1999:blog-9149260308162775442.post-39235890636876847642012-06-29T14:00:43.359+04:002012-06-29T14:00:43.359+04:00Игорб, скажите, а почему вы решили, что второе реш...Игорб, скажите, а почему вы решили, что второе решение O(N)? Линейную сложность имеет сама по себе сортировка корзинками, а изменённая под подсчёт количества инверсий - уже нет.<br /><br />Внешний цикл исполняется N раз явно. Про итоговую линейную сложность можно говорить, если тело цикла исполняется за O(1), а это не так. Там есть два отдельных цикла, один из которых O(количество корзинок), а второй O(размер корзинки). Если мы фиксируем количество корзинок (принимаем за константу), то размер корзинки пропорционален N, и, таким образом, цикл поиска точки вставки имеет линейную сложность. Если заменить его бинарным поиском, будет log(N), и O(N*log(N)) итого, но по связному списку бинарный поиск не сделаешь, а массив даст N на вставке. Итого - квадрат без вариантов.<br /><br />Если же мы фиксируем размер корзинки, то количество корзинок пропорционально N, и цикл подсчёта суммы длин корзинок (в версии из видео) или цикл инкремента кэша инверсий (в версии с everfall) даёт O(N), что в итого даст квадрат. В версии из видео можно сумму считать на дереве Фенвика, тогда получится O(log(N)) тело цикла и O(N*log(N)) итого. Но не более.<br /><br />А так в обоих версиях второго решения у вас квадрат. Проверьте на 100 000 элементов, или на миллионе - будет заметно.Anonymoushttps://www.blogger.com/profile/17152157727140681943noreply@blogger.comtag:blogger.com,1999:blog-9149260308162775442.post-77118173292322317752011-10-02T00:14:07.235+04:002011-10-02T00:14:07.235+04:00Да да, Вы безусловно правы. Там нужно писать в вос...Да да, Вы безусловно правы. Там нужно писать в восьмой строке НОВЫЙ[j]:=ложь по причине, которой Вы сами огласили. <br /><br />Только получается, что цикл будет исполняться на k раз, а k-1, т.к. в шестой строке мы обрабатываем первую вершину цикла, а все последующие k-1 вершины в рамках цикла while.<br /><br />К сожалению опечатки прокрадываются даже в такие шедевральные издания.slipstak2https://www.blogger.com/profile/15957109470497214310noreply@blogger.comtag:blogger.com,1999:blog-9149260308162775442.post-51567846957709890392011-10-01T17:17:29.937+04:002011-10-01T17:17:29.937+04:00Это код из книги Липского, я думаю он не правильны...Это код из книги Липского, я думаю он не правильный.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-9149260308162775442.post-67075477143266435692011-09-30T09:11:14.228+04:002011-09-30T09:11:14.228+04:00"Липский. Комбинаторика для программистов. 19..."Липский. Комбинаторика для программистов. 1988 <br />Особое внимание нужно уделить понятиям инверсии перестановки и знаку перестановки.<br /><br />sgn(f) = pow(-1,I(f)), "<br /><br />В книге(стр 19):<br />1: begin <br />2: s := 1; <br />3: for i := I to n do HOBbII[i]:=ИCTИHА; <br />4: for i := I to n do <br />5: if HOBЫЙ[i] then (*найден цикл, содержащий i*) <br />6: begin <br /> j := P[i]; <br />7: while j <> i do <br />8: begin HOBЫЙ[i]:=ложь; s := -s; j := P[j]; <br />end; <br />end; <br />end; <br /><br />Мне кажется что в коде ошибка, HOBЫЙ[i]:=ложь; должно быть HOBЫЙ[j]:=ложь;<br /><br />Потому что инчае не имеет смысла отмечать HOBЫЙ[i]:=ложь;. <br />Зачем i-ый элемент отмечать k (длина цикла) раз, ведь он уже точно рассмотрен не будет.Anonymousnoreply@blogger.com