Потихоньку начинаем разбирать алгоритмы в программировании, как я и писал ранее. Начнем с самых базовых для повторения и перейдем к более сложным и продвинутым. Я буду давать код алгоритмов на языке Python, так как более продвинутые решения удобнее писать именно на нем. На Solidity не все из них можно будет реализовать "без костылей", но вы сами вполне сможете поэкспериментировать с этим с помощью нейронок.
Понимание алгоритмов также качественно скажется на вашем понимании кода, который вы, возможно, будете писать с помощью редакторов со встроенными нейронными сетями, например Cursor. Итак, приступим!
Введение в алгоритмы и асимптотический (по сути означает "для больших значений") анализ начинается с понимания самой сути алгоритма. Алгоритм представляет собой последовательность четко определенных шагов для решения конкретной задачи, подобно кулинарному рецепту или инструкции по сборке. Например, алгоритм приготовления бутерброда можно описать так: взять два ломтика хлеба, намазать один из них маслом, положить сверху сыр и накрыть вторым ломтиком. Важно, что любой алгоритм предполагает некий набор инструкций, выполнение которых гарантированно приводит к результату.
Однако существует множество способов решить одну и ту же задачу. Рассмотрим процесс поиска нужного документа в архиве. Если документы не упорядочены, придется проверить каждый из них по очереди. Если же они систематизированы, например, в алфавитном порядке, поиск можно осуществить гораздо быстрее, применяя более эффективную стратегию. Эти разные стратегии и являются разными алгоритмами, и их эффективность становится критически важной при работе с большими объемами данных.
Скорость работы алгоритма напрямую зависит от количества обрабатываемых данных. Если в небольшом архиве из десяти дел поиск наугад займет всего несколько секунд, то в хранилище с миллионом документов такой подход потребует непозволительно много времени. Поэтому для оценки эффективности алгоритма используется понятие временной сложности, которая показывает, как количество необходимых операций растет с увеличением размера входных данных. Например, для поиска числа 9 в списке
[3, 7, 1, 9, 5] методом последовательного перебора потребовалось четыре шага. Для списка из ста элементов в худшем случае потребуется сто операций. Эта прямая зависимость описывается линейной сложностью.Для универсального описания скорости алгоритмов используется О-нотация (Big O). Она позволяет классифицировать алгоритмы по их «аппетиту» к ресурсам, предоставляя асимптотическую оценку роста времени выполнения или потребляемой памяти. Основные классы сложности, от наиболее к наименее эффективным, выглядят следующим образом.
1. O(1) — постоянная сложность. Время выполнения не зависит от объема данных.
def get_first_letter(name):
return name[0]
Операция получения первого символа строки всегда выполняется за одно действие, будь то имя «Аня» или «Александр».
2. O(n) — линейная сложность. Время выполнения растет прямо пропорционально размеру входных данных.
def find_element(arr, target):
steps = 0
for item in arr:
steps += 1
if item == target:
return True
return False
Это иллюстрирует простой линейный поиск, где в худшем случае необходимо проверить каждый элемент.
3. O(n²) — квадратичная сложность. Время выполнения пропорционально квадрату количества элементов, что характерно для алгоритмов с вложенными циклами.
def find_all_pairs(arr):
pairs = []
for i in arr:
for j in arr:
pairs.append((i, j))
return pairs
Для массива из пяти элементов будет выполнено 25 итераций, а для тысячи — уже миллион.
4. O(log n) — логарифмическая сложность. Очень эффективный класс, где на каждом шаге объем обрабатываемых данных уменьшается вдвое. Яркий пример — бинарный поиск в отсортированном массиве.