АлкоРитм - Алгоритмы и Структуры данных
Чтобы понять хеш-таблицу, надо написать хеш-таблицу! Привычно считается, что вставка, удаление и получение значения по ключу выполняется за O(1). Так ли это на самом деле? Что такое амортизированная сложность? Зачем и когда делать resize? Проясним окончательно…
Media is too big
VIEW IN TELEGRAM
Концовка видео...
Shrink для хеш-таблицы
(перерасчет при удалении элементов)
Shrink для хеш-таблицы
(перерасчет при удалении элементов)
Media is too big
VIEW IN TELEGRAM
Как вам такой формат объяснений? 🍺
Please open Telegram to view this post
VIEW IN TELEGRAM
This media is not supported in your browser
VIEW IN TELEGRAM
А мы продолжаем...
В базовой части курса:
✅ разобрали основные темы
✅ решили по 5 задач на каждую тему
✅ закрепили знания решением 20 задач
В итоге: 70 решеных задач.
Настало время двигаться дальше!
Открывают вторую часть (название пока не придумал) деревья и обходы в глубину/ширину.
ПРИСОЕДИНЯЙСЯ🍺
В базовой части курса:
В итоге: 70 решеных задач.
Настало время двигаться дальше!
Открывают вторую часть (название пока не придумал) деревья и обходы в глубину/ширину.
ПРИСОЕДИНЯЙСЯ
Please open Telegram to view this post
VIEW IN TELEGRAM
Media is too big
VIEW IN TELEGRAM
Ваше мнение?
Такое объяснение:
🍺 - душняцкая душнота
✅ - полезная душнота
П.С. Буду рад дополнительным комментам
Такое объяснение:
П.С. Буду рад дополнительным комментам
Please open Telegram to view this post
VIEW IN TELEGRAM
АлкоРитм - Алгоритмы и Структуры данных
Как вам такой формат объяснений? 🍺
Media is too big
VIEW IN TELEGRAM
Второй пошел 🍺
Please open Telegram to view this post
VIEW IN TELEGRAM
Други, все чаще всплывают новости про блокировку/замедление телеграм.
В ВК есть группа. Там никакой движухи, только видео с ютуба.
Присоединяйтесь, чтобы не потеряться...
В ВК есть группа. Там никакой движухи, только видео с ютуба.
Присоединяйтесь, чтобы не потеряться...
Алгоритм Луна - способ проверить, корректен ли номер (карты, ИНН, IMEI и т.д.) по контрольной цифре.
❌ Не проверяет, существует ли карта.
✅ Проверяет, правильно ли пользователь ввел данные / битые данные / и т.д.
Номер карты:
5106 2110 1025 5079
1 шаг:
Последняя цифра - контрольная. Начинаем с предпоследней.
Каждую вторую цифру умножаем на 2.
Если получилось значение больше 9 - вычитаем 9.
5 1 0 6 _ 2 1 1 0 _ 1 0 2 5 _ 5 0 7 9
1 0 4 2 2 4 1 5
2 шаг:
Далее суммируем все числа.
9 + 5 + 0 + 1 + 5 + 4 + 0 + 2 + 0 + 2 + 1 + 4 + 6 + 0 + 1 + 1 = 41
3 шаг:
Если сумма делится на 10 без остатка - номер корректный.
41 % 10 = 1 - Номер невалидный по Луну.
Просто картинка из Интернета
Алгоритм построен так, что:
• изменение одной цифры почти всегда ломает сумму;
• перестановка цифр часто обнаруживается;
Ловит большинство случайных ошибок.
Номер карты:
5106 2110 1025 5079
1 шаг:
Последняя цифра - контрольная. Начинаем с предпоследней.
Каждую вторую цифру умножаем на 2.
Если получилось значение больше 9 - вычитаем 9.
5 1 0 6 _ 2 1 1 0 _ 1 0 2 5 _ 5 0 7 9
1 0 4 2 2 4 1 5
2 шаг:
Далее суммируем все числа.
9 + 5 + 0 + 1 + 5 + 4 + 0 + 2 + 0 + 2 + 1 + 4 + 6 + 0 + 1 + 1 = 41
3 шаг:
Если сумма делится на 10 без остатка - номер корректный.
41 % 10 = 1 - Номер невалидный по Луну.
Просто картинка из Интернета
Алгоритм построен так, что:
• изменение одной цифры почти всегда ломает сумму;
• перестановка цифр часто обнаруживается;
Ловит большинство случайных ошибок.
Please open Telegram to view this post
VIEW IN TELEGRAM
Лайвфак
Если на leetcode вы решаете задачи на Кучу/Heap, вам не обязательно тащить Кучу за собой (по крайней мере для Swift).
Leetcode поддерживает swift-collections. Можно использовать Кучу из-под капота.
Официальных постов не нашел, но это легко проверить (см. скрин).
Присоединиться к курсу AlcoRhythm.
П.С. Пульни реакцию, если было полезно🔥
Если на leetcode вы решаете задачи на Кучу/Heap, вам не обязательно тащить Кучу за собой (по крайней мере для Swift).
Leetcode поддерживает swift-collections. Можно использовать Кучу из-под капота.
Официальных постов не нашел, но это легко проверить (см. скрин).
Присоединиться к курсу AlcoRhythm.
П.С. Пульни реакцию, если было полезно
Please open Telegram to view this post
VIEW IN TELEGRAM
14 февраля ❤️
Говорят, что настоящую любовь невозможно найти перебором. Сердечный стек переполнится задолго до нахождения нужного элемента. А описать уже найденную любовь вполне реально.
Связный список - отношения на расстоянии: каждый сам по себе, но ссылка хранится.
Дерево - классическая любовь: у нее есть корни, много потомков и, возможно, пара багов.
Граф - любовный треугольник. Лучше не надо.
Хеш-таблица - идеальная пара: "Ты мой ключ, я твое значение".
Пусть ваши отношения будут как красно-черное дерево: сложно, но сбалансированно. Пусть любовь/код будет чистым, а промокод - активным:
❤️ Влюбленным в скидки: FEB14
✅ Вместо валентинки
Говорят, что настоящую любовь невозможно найти перебором. Сердечный стек переполнится задолго до нахождения нужного элемента. А описать уже найденную любовь вполне реально.
Связный список - отношения на расстоянии: каждый сам по себе, но ссылка хранится.
Дерево - классическая любовь: у нее есть корни, много потомков и, возможно, пара багов.
Граф - любовный треугольник. Лучше не надо.
Хеш-таблица - идеальная пара: "Ты мой ключ, я твое значение".
Пусть ваши отношения будут как красно-черное дерево: сложно, но сбалансированно. Пусть любовь/код будет чистым, а промокод - активным:
Please open Telegram to view this post
VIEW IN TELEGRAM
ups: НОВЫЙ ВИДОСИК
Смотреть обязательно, если:
✅ любите натягивать алгоритмические задачки на реальные;
✅ не понимаете, где может пригодиться "объединение нескольких массивов в один";
✅ дошли до Кучи на курсе.
Смотреть обязательно, если:
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
Вчера добраться до сотки не позволили правила LIFO/FIFO, но сегодня рекорд зафиксирован!
Мы - сет из 100 элементов. Каждый по-своему уникален, каждый хранит свои данные и свой неповторимый опыт.
Please open Telegram to view this post
VIEW IN TELEGRAM
array.sort()
Вы когда-нибудь задумывались как работает сортировка из-под капота?
Возможно, это Quick sort?
Возможно, Merge Sort?
А, возможно, собственная секретная разработка?
За всех говорить не могу, но расскажу о таком подходе как Introsort.
Introsort (Introspective sort) = QuickSort + HeapSort + InsertionSort
Алгоритм сортировки, предложенный Дэвидом Мюссером[англ.] в 1997 году
___
Зачем столько сложностей❓
Изначально применяется QuickSort, НО в худшем случае он даст O(n²). Такая ситуация может произойти при неудачном выборе pivot.
Пример: отсортированный массив + pivot - последний элемент.
Можно выбирать опорный элемент при помощи median-of-three (первый, средний, последний - выбираем средний по величине). Метод хорошо работает на большинстве входных данных, но возможно найти такие входные данные, которые сильно замедлят алгоритм сортировки.
Еще один минус QuickSort - рекурсия, а точнее возможное переполнение стека. Например, лимит 2 * log n (при нормальном разбиении глубина рекурсии примерно log n). Если глубина стала больше, разбиение плохое, а, следовательно, риск O(n²).
___
Если глубина рекурсии слишком большая, переключаемся на HeapSort.
HeapSort дает гарантированное O(n log n), но в среднем работает медленнее.
___
InsertionSort применяется, когда размер подмассива маленький (меньше 16 или 32 элементов).
Почему в игру вступает InsertionSort❓
• рекурсия и partition становятся дороже
• insertion sort быстрее на маленьких массивах
• insertion sort почти линейный на почти отсортированных данных
___
Тезисно:
✅ Introsort - инженерный компромисс между скоростью и гарантией.
✅ InsertionSort - оптимизация для маленьких массивов.
✅ HeapSort - защита от деградации.
✅ QuickSort - основная рабочая лошадь.
Вы когда-нибудь задумывались как работает сортировка из-под капота?
Возможно, это Quick sort?
Возможно, Merge Sort?
А, возможно, собственная секретная разработка?
За всех говорить не могу, но расскажу о таком подходе как Introsort.
Introsort (Introspective sort) = QuickSort + HeapSort + InsertionSort
Алгоритм сортировки, предложенный Дэвидом Мюссером[англ.] в 1997 году
___
Зачем столько сложностей
Изначально применяется QuickSort, НО в худшем случае он даст O(n²). Такая ситуация может произойти при неудачном выборе pivot.
Пример: отсортированный массив + pivot - последний элемент.
Можно выбирать опорный элемент при помощи median-of-three (первый, средний, последний - выбираем средний по величине). Метод хорошо работает на большинстве входных данных, но возможно найти такие входные данные, которые сильно замедлят алгоритм сортировки.
Еще один минус QuickSort - рекурсия, а точнее возможное переполнение стека. Например, лимит 2 * log n (при нормальном разбиении глубина рекурсии примерно log n). Если глубина стала больше, разбиение плохое, а, следовательно, риск O(n²).
___
Если глубина рекурсии слишком большая, переключаемся на HeapSort.
HeapSort дает гарантированное O(n log n), но в среднем работает медленнее.
___
InsertionSort применяется, когда размер подмассива маленький (меньше 16 или 32 элементов).
Почему в игру вступает InsertionSort
• рекурсия и partition становятся дороже
• insertion sort быстрее на маленьких массивах
• insertion sort почти линейный на почти отсортированных данных
___
Тезисно:
Please open Telegram to view this post
VIEW IN TELEGRAM
Началось...
Плавно запускаются стажировки и теплеет на улице. Алгоритмы лучше учить сейчас, пока вокруг грязь и слякоть💡
Не теряйся, присоединяйся💖
Плавно запускаются стажировки и теплеет на улице. Алгоритмы лучше учить сейчас, пока вокруг грязь и слякоть
Не теряйся, присоединяйся
Please open Telegram to view this post
VIEW IN TELEGRAM
TimSort
TimSort - гибридный алгоритм сортировки, опубликованный в 2002 году Тимом Петерсом.
Если верить Википедии:
В настоящее время является стандартным алгоритмом сортировки в Python, OpenJDK 7, Apple Swift Standard Library 5 и реализован в Android JDK 1.5.
___
Основная идея
В реальной жизни данные почти никогда не полностью случайные. Они частично отсортированы.
TimSort создан под реальный мир, а не под худший теоретический случай.
__
Общая идея алгоритма
• разделить входной массив на уже отсортированные подмассивы;
• если подмассив небольшой, применить Insertion Sort;
• объединить полученные подмассивы через Merge Sort.
___
Ключевой момент - runs (уже отсортированный кусок массива).
TimSort проходит по массиву слева направо:
• если последовательность возрастает - оставляем без изменений;
• если убывает - переворачиваем.
TimSort вводит параметр minRun (обычно 32–64).
Откуда такое значение?
Мелкие куски плохо мержить. Накладные расходы начинают доминировать.
Если найденный run слишком маленький, он расширяется с помощью Insertion Sort до minRun.
___
Что происходит дальше?
Все найденные runs складываются в стек. Но не просто "положил и забыл", проверяется условие:
a, b, c - три верхних runs.
а > b + c
b > с
Это необходимо, чтобы глубина стека была O(log n) для сбалансированного слияния без деградации).
___
Фишка TimSort - galloping mode
Пример: Объединяем 2 массива
first: 1 2 3 4 5 6 7 8 9 10
second: 100 101 102
Сравниваем 1 и 100, берем 1
Сравниваем 1 и 101, берем 1
Сравниваем 1 и 102, берем 1
Бесполезные действия, согласитесь. В таких ситуациях подключается galloping mode.
Если один run "выигрывает" слишком часто подряд, перестаем сравнивать по одному элементу. Выполняем экспоненциальный поиск границы (по факту бинарный поиск).
first[i + 1]
first[i + 2]
first[i + 4]
first[i + 8]
first[i + 16]
Ищем место, где элементы перестанут быть меньше second[j]. После этого TimSort возвращается в обычный режим.
___
Сложность TimSort
• Отсортированный массив - O(n)
• Почти отсортированный массив - близко к O(n)
• Случайная последовательность - O(n log n)
• Худший - O(n log n)
TimSort - гибридный алгоритм сортировки, опубликованный в 2002 году Тимом Петерсом.
Если верить Википедии:
В настоящее время является стандартным алгоритмом сортировки в Python, OpenJDK 7, Apple Swift Standard Library 5 и реализован в Android JDK 1.5.
___
Основная идея
В реальной жизни данные почти никогда не полностью случайные. Они частично отсортированы.
TimSort создан под реальный мир, а не под худший теоретический случай.
__
Общая идея алгоритма
• разделить входной массив на уже отсортированные подмассивы;
• если подмассив небольшой, применить Insertion Sort;
• объединить полученные подмассивы через Merge Sort.
___
Ключевой момент - runs (уже отсортированный кусок массива).
TimSort проходит по массиву слева направо:
• если последовательность возрастает - оставляем без изменений;
• если убывает - переворачиваем.
TimSort вводит параметр minRun (обычно 32–64).
Откуда такое значение?
Мелкие куски плохо мержить. Накладные расходы начинают доминировать.
Если найденный run слишком маленький, он расширяется с помощью Insertion Sort до minRun.
___
Что происходит дальше?
Все найденные runs складываются в стек. Но не просто "положил и забыл", проверяется условие:
a, b, c - три верхних runs.
а > b + c
b > с
Это необходимо, чтобы глубина стека была O(log n) для сбалансированного слияния без деградации).
___
Фишка TimSort - galloping mode
Пример: Объединяем 2 массива
first: 1 2 3 4 5 6 7 8 9 10
second: 100 101 102
Сравниваем 1 и 100, берем 1
Сравниваем 1 и 101, берем 1
Сравниваем 1 и 102, берем 1
Бесполезные действия, согласитесь. В таких ситуациях подключается galloping mode.
Если один run "выигрывает" слишком часто подряд, перестаем сравнивать по одному элементу. Выполняем экспоненциальный поиск границы (по факту бинарный поиск).
first[i + 1]
first[i + 2]
first[i + 4]
first[i + 8]
first[i + 16]
Ищем место, где элементы перестанут быть меньше second[j]. После этого TimSort возвращается в обычный режим.
___
Сложность TimSort
• Отсортированный массив - O(n)
• Почти отсортированный массив - близко к O(n)
• Случайная последовательность - O(n log n)
• Худший - O(n log n)
АлкоРитм - Алгоритмы и Структуры данных
array.sort() Вы когда-нибудь задумывались как работает сортировка из-под капота? Возможно, это Quick sort? Возможно, Merge Sort? А, возможно, собственная секретная разработка? За всех говорить не могу, но расскажу о таком подходе как Introsort. Introsort…
Please open Telegram to view this post
VIEW IN TELEGRAM