#algo #math #video
О том, как вывести формулу, описывающую распределение ещё не отсортированной части массива при сортировке пузырьком.
youtu.be/Gm8v_MR7TGk
О том, как вывести формулу, описывающую распределение ещё не отсортированной части массива при сортировке пузырьком.
youtu.be/Gm8v_MR7TGk
YouTube
The Bubble Sort Curve
A derivation of the curve that is approximated by a common visualization of the bubble sort diagram.
Read the full proof on my site: https://linesthatconnect.github.io/blog/a-rigorous-derivation-of-the-bubble-sort-curve/
After uploading, I learned that…
Read the full proof on my site: https://linesthatconnect.github.io/blog/a-rigorous-derivation-of-the-bubble-sort-curve/
After uploading, I learned that…
🔥8🤔2👍1
#algo #article
Пусть у нас есть n элементов, каждый из которых указывает сам на себя. Как мы можем поменять связи так, чтобы объединить эти элементы в некий один цикл, и при этом мы могли бы получить каждый из вариантов перестановки связей с одинаковой вероятностью?
Про это есть Sattolo's algorithm, про который пишет небезызвестный Dan Luu. Он рассказывает не только о самом алгоритме, но и о том, почему он достигает поставленной цели — и при этом не предполагает наличия знаний по комбинаторике (как про это рассказывают в других источниках). Как ни странно, алгоритм Саттоло является минимальной модификацией алгоритма Фишера-Йетса — алгоритма для построения случайной перестановки.
Пусть у нас есть n элементов, каждый из которых указывает сам на себя. Как мы можем поменять связи так, чтобы объединить эти элементы в некий один цикл, и при этом мы могли бы получить каждый из вариантов перестановки связей с одинаковой вероятностью?
Про это есть Sattolo's algorithm, про который пишет небезызвестный Dan Luu. Он рассказывает не только о самом алгоритме, но и о том, почему он достигает поставленной цели — и при этом не предполагает наличия знаний по комбинаторике (как про это рассказывают в других источниках). Как ни странно, алгоритм Саттоло является минимальной модификацией алгоритма Фишера-Йетса — алгоритма для построения случайной перестановки.
🤔2👍1
Data Secrets
Исследователи из Пекина предложили алгоритм поиска кратчайших путей, который обходит Дейкстру Почти 70 лет ученые пытались сломать барьер сортировки для этой задачи. В данной работе это получилось впервые. Разбираемся ⬇️ Классический Дейкстра устроен так:…
#algo
Исторические новости, однако.
Из списка литературы узнал, что конкретно для случая положительных целочисленных весов на направленных графах есть алгоритм нахождения кратчайшего пути с вообще линейной по количеству рёбер временной и пространственной сложностью.
Исторические новости, однако.
Из списка литературы узнал, что конкретно для случая положительных целочисленных весов на направленных графах есть алгоритм нахождения кратчайшего пути с вообще линейной по количеству рёбер временной и пространственной сложностью.
❤7👍2
#prog #amazingopensource #article (и даже в какой-то мере #algo)
Stacktower.io (репозиторий) — инструмент для создания визуализаций зависимостей в духе известного комикса xkcd + история о его создании, с инкрементальным улучшением, начиная с брутфорса. История хорошо демонстрирует, насколько хорошо помогает знать prior art в computer science.
Stacktower.io (репозиторий) — инструмент для создания визуализаций зависимостей в духе известного комикса xkcd + история о его создании, с инкрементальным улучшением, начиная с брутфорса. История хорошо демонстрирует, насколько хорошо помогает знать prior art в computer science.
👍16🌚3❤🔥2❤1