Python_No_Panic

2023-03-05 23:19:57 Зачем нам методы «heapify» и «heapreplace» у структуры данных «heap» и какая у них временная сложность?

Всем привет! В прошлом посте мы с вами разбирались со структурой данных «heap». Сегодня мы продолжим с вами наше знакомство с ее методами. Мы рассмотрим методы: «heapify» и «heapreplace». И так по нашей традиции мы предлагаем вам взять какой-нибудь весенний напиток и устремиться к анализу материала. И так понеслись:

Метод «heapify» преобразовывает список в кучу:

import heapq

lst = [5, 3, 7, 1]

heapq.heapify(lst)

print(lst) # Вывод: [1, 3, 7, 5]

Метод «heapreplace» удаляет наименьший элемент из кучи и добавляет новый элемент за одну операцию:

import heapq

heap = [1, 3, 7, 5]

smallest = heapq.heapreplace(heap, 2)

print(smallest) # Вывод: 1
print(heap) # Вывод: [2, 3, 7, 5]

Временная сложность «heappush», «heappop» «heapreplace» равна O(log n), где n — количество элементов в куче. Временная сложность «heapify» равна O(n), где n — количество элементов в списке.

Надеемся наш материал был интересен для вас. Мы ждем ваших реакций и комментариев под этим постом.

Отличного вам завершения дня и хорошего настроения! Открыть/Комментировать

2023-03-01 12:56:51 Что такое heap и как использовать эту структуру данных на Python

Всем привет! В прошлом посте мы с вами разбирали очень крутой алгоритм сортировки, но как вы помните, не совсем был прост этот малый. Сегодня мы поговорим с вами про интересную структуру данных и ее использование на Python. Встречайте нашего героя - «heap» или «куча». Пост будет в двух частях, не забудьте про ваш теплый напиток или может уже холодненький, вроде уже теплеет. И так поехали:

Структура данных кучи представляет собой структуру данных на основе двоичного дерева, в которой каждый узел либо больше или равен (максимальная куча), либо меньше или равен (минимальная куча) своих дочерних элементов. В Python модуль «heapq» обеспечивает реализацию структуры данных кучи.

Вот пример того, как создать кучу в Python:

import heapq

heap = []

heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)


print(heap) # Вывод: [1, 3, 7, 5]

Функция «heappush» добавляет элемент в кучу и поддерживает свойство кучи. Наименьший элемент всегда находится в корне кучи.

Чтобы удалить наименьший элемент из кучи, вы можете использовать функцию «heappop»:

import heapq

heap = [1, 3, 7, 5]

smallest = heapq.heappop(heap)

print(smallest) # Вывод: 1
print(heap) # Вывод: [3, 5, 7]

В следующем посте мы поговорим с вами про временную сложность наших методов, а также разберем методы: «heapify», «heapreplace».

Ставьте ваши реакции на этот пост, если он вам понравился, также мы всегда рады вас услышать в комментариях.

Всем классного дня! Открыть/Комментировать

2023-03-01 00:46:20 Реализация и анализ алгоритма Quicksort

Всем привет!
В прошлом посте мы разбирали merge sort, а сегодня поговорим про один из самых крутых алгоритмов сортировки - quicksort. И так по нашей традиции мы советуем вам налить чаю и погрузится в чтение нашего материала.

Что за алгоритм?

Быстрая сортировка — это широко используемый алгоритм сортировки, использующий подход «разделяй и властвуй» для сортировки массива элементов. Он был разработан Тони Хоаром в 1959 году и до сих пор считается одним из самых эффективных алгоритмов сортировки.

Реализация алгоритма:

def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return quicksort(left) + [pivot] + quicksort(right)

Функция quicksort() принимает на вход массив arr и сортирует его с помощью алгоритма quicksort. Алгоритм работает, выбирая опорный элемент, разбивая массив вокруг опоры и рекурсивно сортируя подмассивы.

Вот как работает алгоритм:
Если длина массива меньше или равна 1, массив уже отсортирован и мы можем просто вернуть его.
В противном случае мы выбираем опорный элемент (в данном случае первый элемент массива).
Мы разбиваем массив на два подмассива: один содержит все элементы, меньшие опорного, а другой содержит все элементы, большие или равные опорному.
Мы рекурсивно сортируем два подмассива, вызывая quicksort() для каждого из них.
Мы объединяем отсортированные подмассивы со сводным элементом между ними.

Временная сложность:
O(n*log n)

Надеемся вам понравился наш пост. Оставляйте ваши реакции и пишите комментарии.

Суперского вам настроения!

#learning_python_algorithms Открыть/Комментировать

2023-02-25 20:14:32 Всем привет!
Сегодня мы поговорим про merge sort и проанализируем его.
Читайте этот пост, нажав на это предложение

#learning_python_algorithms Открыть/Комментировать

2023-02-23 18:53:24 Подход «divide-and-conquer» в программировании

Всем привет! В прошлом посте мы говорили об Insertion Sort. А сегодня нам нужно двигаться дальше в нашей подготовке к собеседованию на крутую работу. Сегодня мы поговорим с вами про подходы в программировании. Начнем мы с подхода «разделяй и властвуй». И так давайте узнаем что это такое и зачем нам вообще знать про этот подход :) И так начнем!

Подход «разделяй и властвуй» — это стратегия решения проблем, которая включает в себя разбиение большой проблемы на более мелкие подзадачи, их независимое решение, а затем объединение решений для исходной проблемы.

Подход «разделяй и властвуй» работает путем рекурсивного разделения проблемы на более мелкие подзадачи до тех пор, пока они не станут достаточно простыми для непосредственного решения. Затем решения подзадач объединяются для получения решения исходной задачи. Ключевая идея этого подхода заключается в том, что если мы можем эффективно решить подзадачи, то мы также сможем эффективно решить исходную задачу.

Подход «разделяй и властвуй» используется во многих алгоритмах.

К примеру, в алгоритмах сортировки: Merge Sort and Quick Sort.

Или в алгоритмах поиска: Binary Search

А также в алгоритмах умножения матриц: Strassen's Algorithm.

Основные этапы подхода «разделяй и властвуй»:

Разделите проблему на более мелкие подзадачи.
Сделайте эффективное и правильное решение для подзадачи.
Объедините решения подзадач, чтобы получить решение исходной задачи.

Подход «разделяй и властвуй» — это мощная техника решения проблем, которую можно использовать для эффективного решения многих сложных задач. Однако важно правильно выбирать подзадачи и верно комбинировать их решения, чтобы получить желаемый результат.

Надеемся вы узнали что-то новое из нашего поста. Оставляйте свои комментарии и реакции под этим материалом.

Всем отличного настроения и продолжения дня!

#learning_python_algorithms Открыть/Комментировать

2023-02-22 00:10:03 Реализация и анализ Insertion Sort

Всем привет!
Мы продолжаем радовать вас контентом, который обычно заставляет нас боятся собеседований. Надеемся вы пытаетесь осмыслить все алгоритмы, которые мы тут с вами разбираем, ведь совсем скоро вступим в бой с задачками на лит код и будем устранять все пробелы в наших знаниях.
Если вы забыли про что мы говорили в предыдущем посте, то мы советуем освежить его в памяти, перейдя по этой ссылке. А теперь вернемся к нашим красивым алгоритмам :)

Сегодня разговор пойдет про insertion sort.
Алгоритм работает, перебирая массив и вставляя каждый элемент в правильное положение в отсортированной части массива.

Реализация алгоритма:

def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key

Вот как работает алгоритм:

Мы начинаем со второго элемента массива (i=1) и предполагаем, что первый элемент (i=0) уже отсортирован.
Мы сохраняем текущий элемент в переменной с именем key.
Мы сравниваем ключ с каждым предшествующим ему элементом (j=i-1), начиная с последнего элемента отсортированной части массива, и перемещаем все элементы, которые больше ключа, на одну позицию вправо.
Мы вставляем ключ в правильное положение в отсортированной части массива, вставляя его после последнего элемента, который меньше или равен ключу.
Мы повторяем этот процесс для каждого элемента массива.

Временная сложность:
O(n)

Надеемся вам нравится наш материал. Если у вас есть какие-то предложения или идеи, то не стесняйтесь их озвучивать в комментариях. Мы желаем вам успехов в изучении алгоритмов и суперского настроения!

#learning_python_algorithms Открыть/Комментировать

2023-02-18 09:54:26 Реализация и анализ сортировки выбором

Всем привет! Совсем недавно мы говорили с вами про bubble sort - сортировку пузырьком. А теперь пришло время говорить о более быстрых алгоритмах, так как в прошлом посте мы выяснили, что сортировка пузырьком хоть и выполняет свою задачу, но делает это не очень эффективно. И так начнем:

Сортировка выбором — это простой алгоритм сортировки, который многократно находит минимальный элемент из несортированной части массива и помещает его в начало массива. Он работает, выбирая наименьший элемент и заменяя его элементом в текущей позиции, пока весь массив не будет отсортирован.

Вот реализация сортировки выбором в Python:

def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr

Внешний цикл проходит от 0 до n-1, где n — длина массива. На каждой итерации минимальный элемент находится из несортированной части массива (т. е. от i+1 до n-1) с помощью внутреннего цикла. Затем минимальный элемент заменяется элементом в текущей позиции (т. е. i).

Временная сложность:

Временная сложность сортировки выбором O (n ^ 2)

Надеемся вам понравился наш разбор сортировки выбором. Если у вас есть какие-то предложение, то пишите их в комментариях. Также не забудьте поставить вашу реакцию на этот пост, ведь именно это мотивирует нас делать крутой контент.

Всем отличного дня!

#learning_python_algorithms Открыть/Комментировать

2023-02-16 19:19:16 https://telegra.ph/Sekrety-planirovaniya-ch1-12-10

#soft_skills Открыть/Комментировать

2023-02-16 00:05:08 Что такое пузырьковая сортировка

В прошлом посте мы рассказали вам о такой важной теме как словари. А сегодня поговорим о чем-то более замысловатом, но в меру сложном. Мы вправду хотим подробно рассказать вам о том, как пройти техническое интервью не в самые простые компании. Наша задача состоит в том, чтобы помочь вам расти и быть вашим каналом-помощником в обучении. Так что надеемся, что этот пост будет для вам действительно полезен. А теперь к делу!

Пузырьковая сортировка — это простой алгоритм сортировки, который многократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они расположены в неправильном порядке. Алгоритм получил свое название из-за того, что более мелкие элементы «всплывают» вверх списка. Вот реализация Python алгоритма пузырьковой сортировки выглядит следующим образом:

def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]

В приведенном выше коде arr — это список для сортировки, а n — длина списка. Внешний цикл для i в диапазоне (n) проходит через все элементы в массиве. Внутренний цикл для j в диапазоне (0, n-i-1) проходит через несортированную часть списка. Оператор if arr[j] > arr[j+1] проверяет, больше ли текущий элемент, чем следующий элемент, и если это так, то два элемента меняются местами.

Анализ временной сложности:

Временная сложность алгоритма пузырьковой сортировки составляет O(n^2), где n — количество элементов в списке. Это связано с тем, что в худшем случае внутренний цикл будет выполняться n*(n-1) раз, что дает в общей сложности n^2 - n итераций.

Надеемся, что этот пост вам понравился и вы поддержите нашу работу лайком. Если у вас есть предложения или идеи для наших дальнейших постов, то мы готовы вас выслушать и работать как партнеры!

Отличного вам настроения!

#learning_python_algorithms Открыть/Комментировать

2023-02-13 17:52:42 Словари!

В прошлом посте мы с вами говорили про повышение эффективности наших алгоритмов, а сегодня поговорим про такую структуру данных как словарь. Данная структура данных очень часто используется для решения повседневных и технических задач на собеседованиях.

Словарь в Python — это структура данных, которая сопоставляет ключи со значениями. Это неупорядоченный набор пар ключ-значение, где каждый ключ уникален и используется для получения связанного с ним значения. Ключи в словаре могут относиться к любому хешируемому типу данных, например к целым числам, строкам или кортежам, а значения могут относиться к любому типу данных, включая другие словари.

Вот пример того, как вы можете создать и использовать словарь в Python:

Создание словаря

dict = {'key1': 'value1', 'key2': 'value2', 'key3': 'value3'}

Доступ к значениям с помощью ключей

print(dict['key1'])

Вывод: значение1

Добавление новой пары ключ-значение

dict['key4'] = 'value4'

Обновление значения ключа

dict['key1'] = 'new_value1'

Удаление пары ключ-значение

del dict['key2']

Цикл по словарю

for key, value in dict.items():

print(key, ':', value)

Надеемся вам поможет наш материал в устранении пробелов по этой теме. Ставьте ваши лайки и пишите предложения в комментариях. Ваша обратная связь очень цена для нас. Всем отличного настроения! Открыть/Комментировать