Введение в алгоритмы

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

Алгоритмы

Это набор инструкций для выполнения какой-нибудь задачи. Рецепт приготовления шарлотки, правила расстановки запятых, ПДД — это всё алгоритмы.
Хороший кодер понимает как работают алгоритмы и какой подходит для его задания.

Весь код можно считать алгоритмом, но мы будем рассматривать его как набор функций, которые должны выполнить свою задачу. Условно, у алгоритмов есть две характеристики: скорость работы и количество занимаемой памяти.

Скорость работы

Скорость работы выражается в О-большом. Оно показывает насколько сильно растёт количество операций в зависимости от аргумента.

Измерять в секундах не круто, потому что на разных компьютерах стоит разное железо и разная архитектура. Код, который на домашнем ПК выполнится за 3 минуты, на мейнфрейме IBM выполнится за 5 секунд. Поэтому у О-большого нет обозначения единиц измерения, просто значения.

У О-большого есть аргумент — аргумент алгоритма. То есть, какое число стоит в скобках, такое число передается алгоритму на вход.
Например, скорость работы алгоритма = O(n). Это значит, что чтобы пройтись по списку из 16 значений, ему нужно будет 16 операций.
Алгоритму со скоростью работы O(log n) нужна будет 4 операции, потому что O(log n) = O(log 16) = O(4).

В кодинге сложилось несколько основных типов сложностей алгоритмов: линейная, логарифмическая, квадратичная и экспоненциальная. Есть и другие, но встречаются они реже, чем эти.

Чтобы понять смысл графиков, представим что компьютер работает медленно и выполняет одну операцию в секунду.

На самом деле, домашние компьютеры работают в 3 миллиарда раз быстрее.

Количество занимаемой памяти

Чтобы понять сколько памяти нужно для выполнения программы, нужно посчитать объём входных данных, данных для хранения самой функции и объём выходных данных. Существует два способа посчитать объём памяти: посчитать руками или через скрипт.

Руками
Выделяем кусок кода и смотрим, какие данные и операции там есть. Число типа int — добавляем 24 байта, строка — добавляем 49 байт и так далее. Мы писали про размеры в статье про типы данных и сколько они занимают.
Если функция рекурсивная, то после подсчёта объёма, нужно умножить его на количество вызовов. После всех подсчётов получится примерное количество используемой памяти в байтах.

a = 7  # Занимает 24 байта
b = 3.0  # Занимает 24 байта

string = 'test'  # Занимает 53 байта: 49 на пустую строку и по байту на каждый символ
# Всего получается 24 + 24 + 53 = 101 байт

Через скрипт
Скачиваем библиотеку memory_profiler через pip3. Пишем в терминале python3 -m memory_profiler имя_файла.py.
Он построчно посчитает код и сразу добавит сколько это займёт вместе с интерпретатором и системными штуками, которые никто не видит.

memory_profiler считает и объём пайтон-интерпретатора, потому что он запускается чтобы выполнить скрипт

Матрицы

Если вы уже изучали матрицы и поняли как они работают, можете листать дальше.

Мы сделали статью про матрицы отдельной, потому что они нужны не только программистам, но ещё и старшеклассникам и первокурсникам физматов.
Погружение в мир матриц.

Матрицы в пайтоне

Чтобы использовать матрицы в пайтоне, нужно установить библиотеку NumPy.

Для винды
pip install numpy

Для линукса/мака
pip3 install numpy

Матрица лежит в памяти как массив. Создаётся матрица вот так

import numpy as np


# Матрица 3×3 с элементами от 0 до 8
matrix = np.arange(9).reshape(3, 3)
print(matrix)

Сложение и вычитание матриц

import numpy as np


matrix_a = np.arange(9).reshape(3, 3)
matrix_b = np.arange(9).reshape(3, 3)

print(matrix_a + matrix_b)
print(matrix_a - matrix_b)

Умножение матрицы на число

import numpy as np


matrix_a = np.arange(9).reshape(3, 3)

print(matrix_a * 3)

Умножение матрицы на матрицу делается через функцию dot

import numpy as np


matrix_a = np.arange(9).reshape(3, 3)
matrix_b = np.arange(9).reshape(3, 3)

print(np.dot(matrix_a, matrix_b))

Возведение в степень

import numpy as np


matrix_a = np.arange(9).reshape(3, 3)
print(np.linalg.matrix_power(matrix_a, 5))

В следующей статье по алгоритмам и математике мы хотим рассказать про числа Фибоначчи.

Поделиться
Отправить
Запинить
 33   4 мес   алгоритмы   математика
Популярное