Алгоритмы: просто о сложном

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

Содержание:
1. Виды алгоритмов
2. Способы записи алгоритмов
3. Виды сортировок
3.1. Сортировка слиянием
3.2. Сортировка вставками
3.3. Быстрая сортировка
4. Алгоритм Евклида
4.1. Особенности простых чисел
5. Алгоритм вычисления чисел Фибоначчи
6. Важность алгоритмов и сферы их применения
Заключение

1. Виды алгоритмов

Различают три вида алгоритмов:

1. Линейный — действия выполняются последовательно и однократно. Например, рецепт приготовления пельменей: поставить воду, добавить соль, довести до кипения, опустить пельмени, варить до готовности.
2. Разветвляющийся — есть условие, в зависимости от соблюдения или несоблюдения которого выполняются разные действия. Например, если идет дождь, взять зонт, если светит солнце, взять очки.
3. Циклический — действия повторяются определенное количество раз. Например, чтение книги: прочитать, перелистнуть страницу, прочитать, перелистнуть страницу и так далее.

2. Способы записи алгоритмов

На практике чаще всего встречаются четыре вида записи алгоритмов: словесный, графический, с помощью псевдокода и программный.

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

Графическое описание обычно представляется в виде блок-схемы. Она состоит из блоков, линий и стрелок. Каждому действию соответствует геометрическая фигура. Например, начало и конец — это овал, ввод/вывод — параллелограмм, выполнение действия — прямоугольник, принятие решения — ромб. Более продвинутые варианты этого подхода реализованы в UML-диаграммах, подробнее можно посмотреть эту нашу подборку: топ-19 сервисов для создания блок-схем и UML.

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

Пример псевдокода:

алг Сумма квадратов (арг цел n, рез цел S)
дано | n > 0
надо | S = 1*1 + 2*2 + 3*3 + ... + n*n
нач цел i
  ввод n; S:=0
  нц для i от 1 до n
    S:=S+i*i
  кц
  вывод "S = ", S
кон

Самый формальный способ записи — программный. Это уже компьютерная программа, которая написана на алгоритмическом языке программирования — например, C, Python, Go или любом другом. Описание строго формализовано, так как предназначено для обработки машиной, а не только человеком.

3. Виды сортировок

Распространенная задача на знание алгоритмов — сортировка элементов списка. Выполнить ее можно разными способами. Все эти способы отличаются скоростью выполнения и эффективностью. Рассмотрим несколько основных методов сортировки. Задача — отсортировать значения в списке по возрастанию.

3.1. Сортировка слиянием

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

После разбиения соседние значения становятся парами. Алгоритм объединяет и сортирует пары между собой, пока не получится новый, отсортированный список.

Пример реализации:

def merge(left_list, right_list):  
    sorted_list = []
    left_list_index = right_list_index = 0

    # Длина списков часто используется, поэтому создадим переменные для удобства
    left_list_length, right_list_length = len(left_list), len(right_list)

    for _ in range(left_list_length + right_list_length):
        if left_list_index < left_list_length and right_list_index < right_list_length:
            # Сравниваем первые элементы в начале каждого списка
            if left_list[left_list_index] <= right_list[right_list_index]:
                sorted_list.append(left_list[left_list_index])
                left_list_index += 1
            # Если первый элемент правого подсписка меньше, добавляем его
            # в отсортированный массив
            else:
                sorted_list.append(right_list[right_list_index])
                right_list_index += 1

        # Если достигнут конец левого списка, элементы правого списка
        # добавляем в конец результирующего списка
        elif left_list_index == left_list_length:
            sorted_list.append(right_list[right_list_index])
            right_list_index += 1
        # Если достигнут конец правого списка, элементы левого списка
        # добавляем в отсортированный массив
        elif right_list_index == right_list_length:
            sorted_list.append(left_list[left_list_index])
            left_list_index += 1

    return sorted_list

def merge_sort(nums):  
    # Возвращаем список, если он состоит из одного элемента
    if len(nums) <= 1:
        return nums

    # Для того чтобы найти середину списка, используем деление без остатка
    mid = len(nums) // 2

    # Сортируем и объединяем подсписки
    left_list = merge_sort(nums[:mid])
    right_list = merge_sort(nums[mid:])

    # Объединяем отсортированные списки в результирующий
    return merge(left_list, right_list)
random_list_of_nums = [120, 45, 68, 250, 176]  
random_list_of_nums = merge_sort(random_list_of_nums)  
print(random_list_of_nums)

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

Сложность алгоритма — O(n log n).

3.2. Сортировка вставками

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

def insertion_sort(nums):  
    # Сортировку начинаем со второго элемента, так как считается, что первый элемент уже отсортирован
    for i in range(1, len(nums)):
        item_to_insert = nums[i]
        # Сохраняем ссылку на индекс предыдущего элемента
        j = i - 1
        # Элементы отсортированного сегмента перемещаем вперед, если они больше элемента для вставки 
        while j >= 0 and nums[j] > item_to_insert:
            nums[j + 1] = nums[j]
            j -= 1
        # Вставляем элемент
        nums[j + 1] = item_to_insert

# Проверяем, что оно работает
random_list_of_nums = [9, 1, 15, 28, 6]  
insertion_sort(random_list_of_nums)  
print(random_list_of_nums)

Сложность алгоритма — O(n²).

3.3. Быстрая сортировка

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

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

Пример реализации:

def partition(nums, low, high):  
    # Выбираем средний элемент в качестве опорного
    pivot = nums[(low + high) // 2]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while nums[i] < pivot:
            i += 1
        j -= 1
        while nums[j] > pivot:
            j -= 1
        if i >= j:
            return j
        nums[i], nums[j] = nums[j], nums[i]
def quick_sort(nums):  
    # Создадим вспомогательную функцию, которая вызывается рекурсивно
    def _quick_sort(items, low, high):
        if low < high:          
            split_index = partition(items, low, high)
            _quick_sort(items, low, split_index)
            _quick_sort(items, split_index + 1, high)
    _quick_sort(nums, 0, len(nums) - 1)

Сложность алгоритма — O(n log n). Однако если опорный элемент равен наименьшему или наибольшему элементу в списке, то сложность вырастает до O(n²).

4. Алгоритм Евклида

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

Первый пример — использование остатка от деления:

def gcd_rem_division(num1, num2):
    while num1 != 0 and num2 != 0:
        if num1 >= num2:
            num1 %= num2
        else:
            num2 %= num1
    return num1 or num2

Алгоритм делает числа меньше, пока одно из них не станет равным нулю, а другое — делителю, который вы ищете. С помощью логического оператора OR в return вы получаете искомый делитель.

Второй пример — использование вычитания:

def gcd_subtraction(num1, num2):
    while num1 != 0 and num2 != 0:
        if num1 >= num2:
            num1 -= num2
        else:
            num2 -= num1
    return num1 or num2

Реализация похожа на первый пример, единственное отличие — вместо деления используется вычитание.

Третий пример — рекурсия:

def gcd_recursion(num1, num2):
    if num1 == 0:
        return num2
    return gcd_recursion(num2 % num1, num1)

Здесь тоже используется остаток от деления, но вместо цикла while работает рекурсия.

Если два переданных числа не имеют общего делителя, то всегда возвращается 1, потому что все числа делятся на 1.

4.1. Особенности простых чисел

Простые числа — это такие числа, которые без остатка делятся сами на себя и на единицу. Например, 2, 3, 5, 7, 11, 13.

Если подать на вход два простых числа, которые не равны друг другу, то на выходе всегда будет 1. Но если простым будет только одно число, то необязательно в результате получится единица.

Например, числа 7 и 21. 7 — простое число, 21 — нет. Вернется 7, потому что 21 делится на 7 без остатка.

5. Алгоритм вычисления чисел Фибоначчи

Числа Фибоначчи — ряд чисел, в котором каждый элемент равен сумме двух предыдущих элементов. Например, 1, 1, 2, 3, 5, 8, 13 и так далее.

Вычислить числа Фибоначчи можно двумя способами: циклом и рекурсией.

Первый пример — с циклом while.

fib1 = 1 // Значение первого элемента ряда
fib2 = 1 // Значение второго элемента ряда
n = input("Номер элемента ряда Фибоначчи: ")
n = int(n)
i = 0
while i < n - 2: // Первые два значения известны, поэтому n-2
    fib_sum = fib1 + fib2
    fib1 = fib2
    fib2 = fib_sum
    i = i + 1
print("Значение этого элемента:", fib2)

Если пользователь введет 1 или 2, то цикл не запустится. На экране сразу отобразится значение fib2.

Второй пример — с циклом for. Здесь на экран выводится весь ряд:

fib1 = fib2 = 1
n = int(input())
print(fib1, fib2, end=' ')
for i in range(2, n):
    fib1, fib2 = fib2, fib1 + fib2
    print(fib2, end=' ')

При рекурсивном вычислении вы сразу задаете проверку элемента. Если он равен 1 или 2, то нужно вернуть 1, так как первый и второй элемент равны 1. Если n > 2, то последовательно выполняется одна и та же функция с аргументами n - 1 и n - 2.

Пример реализации:

def fibonacci(n):
    if n in (1, 2):
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)
 print(fibonacci(10))

Минус рекурсии в том, что на вычислении 1000-го элемента вернется ошибка:

RecursionError: maximum recursion depth exceeded in comparison

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

6. Важность алгоритмов и сферы их применения

Выше мы дали определение алгоритма — это совокупность (последовательность) шагов, которая помогает решить конкретную задачу.

Отсюда вытекают три важные характеристики:

• Конечное время — если действия выполняются бесконечно и не приводят к результату, то в таком алгоритме нет смысла.
• Четкие инструкции — каждый шаг должен быть однозначным.
• Пригодность к использованию — действия должны приводить к решению задачи.

Если следовать общему понятию, то алгоритмы везде — от чистки зубов и приготовления обеда до искусственного интеллекта. Но давайте сузим область до Computer Science и посмотрим на конкретных примерах, какие алгоритмы где применяются.

1. Различные сортировки используются в анализе данных, искусственном интеллекте, анализе связей.
2. Преобразование Фурье используется везде, где есть электронно-вычислительное устройство: в смартфонах, компьютерах, спутниках.
3. Алгоритм Дейкстры помогает решать задачи по поиску кратчайшего пути между двумя узлами. Применение ему находится везде: от сетей до работы приложений по заказу такси.
4. Алгоритм RSA делает криптографию повсеместной и помогает защищать данные.
5. Алгоритмы сжатия данных используются в играх, музыке, видео, фотографиях, базах данных, чтобы удешевить системы и сделать их более эффективными.

Заключение

Мы рассмотрели основы алгоритмов и примеры их реализации на Python. Если хотите узнать больше об алгоритмах и структурах данных, посмотрите видео ниже. Оно предназначено для студентов технических вузов и программистов-самоучек: