Это руководство — для тех, кто только начал изучать алгоритмы и хочет узнать, насколько мощно это прокачает навыки программирования, или для тех, кто не понимает, зачем крупные компании вроде Google, Facebook и Amazon ищут программистов, которые умеют оптимизировать программы.
Что такое алгоритмы
Алгоритм — это последовательность действий для решения задачи. Грубо говоря, алгоритм — это и есть решение задачи.
Задача. Найти n-факториал
Инициализируем переменную fact = 1
Для каждого значения v в диапазоне от 1 до n:
Умножаем fact на v
Ответ: fact
Выше — алгоритм нахождения n-факториала, который записан на русском языке. Если этот же алгоритм записать на каком-нибудь языке программирования, он будет называться кодом.
Например, вот код для решения той же задачи на языке C++.
int factorial(int n) < int fact = 1; for (int v = 1; v return fact; >
Все программирование завязано на структурах данных и алгоритмах. Первые нужны для хранения данных, а вторые — для решения задач с помощью этих данных.
АЛГОРИТМЫ в ПРОГРАММИРОВАНИИ для новичков | Левенштейн, Фибоначчи, Факториал и т.д.
В серии статей о структурах данных и алгоритмах мы подробно поговорим о решении стандартных задач наиболее эффективным способом и научимся оценивать эту самую эффективность.
Структуры данных и алгоритмы для масштабируемости
Время и память — в приоритете
Представим такую ситуацию. Маша и Андрей пытаются решить простую задачу, им нужно найти сумму первых 10 11 натуральных чисел. Пока Андрей прописывал алгоритм, Маша быстренько реализовала его.
Алгоритм Андрея
Инициализируем переменную sum = 0
Для каждого натурального числа n в промежутке от 1 до 1011 включительно:
Добавляем n к sum
Ответ: sum
Код Маши
int findSum() < int sum = 0; for (int v = 1; v return sum; >
Андрей и Маша гордятся собой. Они смогли написать программу и почти не потратили на это времени. Вот, что они говорят друг другу:
Маша: Давай запустим код и узнаем сумму.
Андрей: Я запустил его уже пару минут назад, а ответа все нет и нет. Что не так с этим кодом?
Упс! Что-то пошло не так! Андрей снова пытается запустить программу, но ничего не получается. Давайте разберемся, что не так в этом простом коде.
Два самых ценных ресурса компьютерной программы — это время и память.
Время выполнения программы рассчитывается по этой формуле:
Время выполнения кода = количество инструкций * время на выполнение каждой инструкции
Количество инструкций зависит от длины кода, а время, необходимое для выполнения каждой инструкции, зависит от компьютера и компилятора.
В нашем случае общее количество выполненных инструкций (скажем, x) равно
x = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Предположим, что компьютер выполняет одну инструкции за одну секунду (этот показатель может варьироваться в зависимости от конфигурации «машины»). Тогда время, необходимое для выполнения кода Маши, y = 108.
Время, затраченное на выполнение кода = x / y — более 16 минут.
ВСЯ СЛОЖНОСТЬ АЛГОРИТМОВ ЗА 11 МИНУТ | ОСНОВЫ ПРОГРАММИРОВАНИЯ
Можно ли оптимизировать алгоритм, чтобы Маше и Андрею не приходилось при каждом запуске ждать по 16 минут?
Скорее всего, вы уже догадались о более правильном подходе. Сумму n-первых натуральных чисел можно найти по этой формуле:
Сумма = N * (N + 1) / 2
Преобразуем эту формулу в код:
int sum(int N) < return N * (N + 1) / 2; >
Теперь наш код состоит всего из одной инструкции и выполняет задачу одинаково быстро вне зависимости от значения N. Даже если N будет больше, чем общее количество атомов во Вселенной, компьютер посчитает сумму очень быстро.
Время, необходимое для решения задачи, в этом случае составляет 1/y, то есть 10 наносекунд. На секундочку, время реакции синтеза водородной бомбы составляет 40-50 наносекунд. Поэтому даже если кто-то бросит водородную бомбу на ваш компьютер, программы все равно успеет посчитать сумму n-первых чисел.
Примечание. На самом деле, в нашей оптимизированной программе больше одной инструкции. Каждое арифметическое действие — отдельная инструкция.
Подробнее о масштабируемости
Масштабируемость (scalability) — способность программы справляться с увеличением нагрузки.
Допустим, нам нужно создать класс на 50 ученик. Самое простое решение: арендовать комнату, достать доску, несколько мелков или маркеров — проблема решена.
А что если размеры увеличатся? Например, нам нужно будет усадить уже 200 учеников?
Решение все то же, но потребуются дополнительные ресурсы. Скорее всего, понадобится комната гораздо больше (возможно, придется арендовать театр), проектор и цифровая ручка.
А если нужно усадить 1000 учеников?
Прежнее решение в этом случае уже не сработает или, в лучшем случае, потребует очень много ресурсов. Размеры увеличились, и наше решение не справляется с увеличившейся нагрузкой — оно не масштабируемое.
Можно ли придумать масштабируемое решение этой проблемы?
Можно. Существует образовательный интернет-проект «Академия Хана», который позволяет миллиону учеников одновременно просматривать обучающие видео, читать статьи и так далее. Неважно, сколько людей одновременно учатся: 50 или 10000, дополнительных ресурсов не требуется. Такое решение умеет справляться с увеличением нагрузки — оно масштабируемое.
Вернемся к Маше и Андрею. Их программу по поиску суммы первых n-натуральных чисел нельзя масштабировать. Дело в том, что в их коде с линейным увеличением значения n линейно растет время выполнения программы. Такие алгоритмы называют алгоритмами с линейным масштабированием.
Память — дорогой ресурс
В реальных условиях у вас в распоряжении почти никогда не будет много памяти. Поэтому чем меньше памяти ваша программа тратит, тем лучше. Когда вы пишете код или систему, которая хранит большое количество данных, очень важно по возможности экономить расход памяти.
Например, вам нужно хранить данные о людях, в том числе — об их возрасте. Есть два подхода: можно хранить дату рождения, а можно — возраст. С точки зрения экономии памяти выгоднее хранить возраст. Если понадобится выяснить дату рождения, всегда можно быстро ее посчитать: для этого достаточно вычесть возраст из текущего года.
Примеры эффективности алгоритмов
Давайте рассмотрим несколько примеров того, как структуры данных и алгоритмы помогают в реальной жизни.
Задача 1. Возрастная группа
Задачу по поиску людей определенной возрастной группы можно легко решить с помощью немного измененного алгоритма двоичного поиска. Главное, чтобы данные были предварительно отсортированы.
Самый очевидный подход к решению этой задачи (его можно назвать «наивным») выглядит так: перебрать всех людей друг за другом и каждый раз проверять, попадает ли текущий человек в данную возрастную группу. У такого алгоритма линейная масштабируемость: время выполнения линейно увеличивается с ростом исследуемой группы. А у двоичного поиска — логарифмическая масштабируемость. Это значит, что если «размер» задачи возвести в квадрат, время, необходимое для ее решения, удвоится.
Допустим, для группы из 1.000 человек требуется 1 секунда, чтобы найти всех людей определенного возраста. Если в группе 1.000.000 человек,
- алгоритму двоичного поиска понадобится всего 2 секунды;
- «наивному» алгоритм понадобится 1 миллион секунд.
Тот же алгоритм двоичного поиска используется для нахождения квадратного корня числа.
Задача 2. Кубик Рубика
Представьте, что вы пишете программу, которая «решает» кубик Рубика.
У кубика 43 252 003 274 489 856 000 возможных позиций. Представьте себе, сколько путей можно пройти и, в итоге, все равно попасть в неправильную позицию.
К счастью, решить эту задачу можно с помощью такой структурой данных как графы. На них завязан алгоритм Дейкстры, он позволяет решить эту задачу за линейное время (не путать с линейной масштабируемостью).
Задача 3. ДНК
ДНК — это молекула, несущая генетическую информацию. В состав ДНК входят азотистые основания, которые обозначаются латинскими буквами: A (аденин), C (цитозин), T (тимин) и G (гуанин).
Представим, что вы работаете в сфере биоинформатики. Вам поручают выявить, есть ли в цепи ДНК заданный паттерн (шаблон).
Это достаточно известная задача в программировании, особенно в научных кругах. Самое простое решение займет время, пропорциональное количеству символов в цепи ДНК, умноженному на количество символов в шаблоне.
(количество символов в цепи ДНК) * (количество символов в шаблоне)
Обычно ДНК-цепь состоит из миллиона азотистых оснований. Но не волнуйтесь, алгоритм Кнута — Морриса — Пратта (КМП) поможет решить эту задачу за время, пропорциональное сумме количества символов в цепи ДНК и символов в шаблоне.
(количество символов в цепи ДНК) + (количество символов в шаблоне)
1.2. Разработка структур данных и алгоритмов
На этапе разработки для коллекции выбираются программная структура хранения данных и алгоритмы её операций. Но в рамках лабораторных работ программная структура данных для хранения коллекции и набор основных операций задаётся вариантом задания. Необходимо спроектировать программный объект коллекции, реализующий заданный вариант.
Для реализации коллекции используется объектно-ориентированный подход к проектированию. Коллекция представляется в виде объекта, объединяющего в единое целое данные и операции. Основой для проектирования структуры коллекции служит формат АТД, составленный на этапе постановки задачи. Раздел данных АТД определяет набор полей объекта коллекции, а раздел операций – набор методов.
В раздел данных коллекции вводятся именованные поля для общих параметров коллекции, определенных в АТД (предельный размер коллекции, текущий размер коллекции и т.п.) и структура данных, хранящая данные, включаемые в коллекцию. Впоследствии, по мере разработки методов объекта, для них в раздел данных вводятся вспомогательные поля и структуры данных (адрес массива или адрес первого элемента связной структуры, индекс или адрес последнего элемента, адрес текущего элемента, структура для вспомогательной очереди или стека и т.п.).
Все перечисленные выше категории полей помещаются в скрытую секцию коллекции и защищены от непосредственного доступа к ним клиентской программы, использующей коллекцию.
Для представления структуры, хранящей множество данных, применяются две альтернативные формы – массив или связная структура на основе указателей. Учитывая произвольное количество данных, включаемых в коллекцию, как правило, массив или связная структура размещаются в динамической памяти.
В случае использования связной структуры возникает необходимость в представлении отдельного элемента структуры, хранящего не только значение объекта, но и указатели на соседние элементы структуры. Поэтому в коллекцию вводится вспомогательный объект для отдельных элементов структуры (элемент списка, узел дерева, вершина графа и т.п.). По мере пополнения коллекции новыми данными создаются вспомогательные объекты – элементы структуры и включаются в связную структуру. Эти элементы, как и сама структура, являются внутренними для коллекции и скрыты от клиентской программы.
Особо необходимо отметить разработку для коллекции дополнительных объектов – итераторов. Необходимость итераторов связана с особенностями реализации коллекции. Поскольку данные, включённые в коллекцию, хранятся во внутренних элементах скрытой структуры, то доступ к данным для клиентской программы становится не тривиальной задачей.
Итератор позволяет клиентской программе получить доступ к значениям данных, скрытых в коллекции, играя роль обобщенного указателя на данные, хранящиеся в коллекции. Он даёт возможность перемещаться по данным и, чаще всего, используется в программах, выполняющих перебор всех данных, хранящихся в коллекции.
Все эти манипуляции возможны, благодаря операциям итератора, аналогичным по действию операциям адресной арифметики над адресными указателями. Но операции итератора учитывают специфику организации внутренней структуры коллекции. Поэтому разработка итератора является частью разработки коллекции. В коллекции определяется встроенный тип для создания итератора. Но в отличие от внутренних элементов структуры, итераторы является внешними объектами по отношению к коллекции и создаются клиентской программой с использованием этого встроенного типа.
Как и любой объект, итератор имеет данные – ссылку на объект коллекции, к которому он привязан, ссылку на текущий элемент скрытой структуры коллекции, хранящий отдельное данное, методы установки итератора на первый или последний элементы коллекции, перемещения по элементам, обнаружения конца просмотра.
Таким образом, в среде клиентской программы структуру отдельного объекта – коллекции можно изобразить с помощью типовой схемы, приведенной на рисунке 1.
Рис. 1. Структура объекта коллекции.
Далее на этапе реализации следует разработка интерфейса коллекции. Интерфейс коллекции определяется набором методов, с помощью которых клиентская программа может манипулировать данными, хранящимися в коллекции, и коллекцией в целом. Прежде всего, в этот набор включаются операции, заданные в АТД. Формат АТД задаёт точную спецификацию операций: их назначение, входные параметры и результаты, ограничения для входных параметров. На основе этой спецификация задаются программные заголовки методов с указанием типов и имен их входных переменных.
Если при разработке методов, оговоренных в АТД, возникает необходимость в дополнительных методах, необходимых для управления коллекцией, то они вводятся в интерфейс коллекции и, соответственно, в формат АТД.
Все интерфейсные методы помещаются в секцию объекта коллекции, открытую для клиентских программ.
Алгоритмы методов реализуют операции, указанные в АТД, с учётом выбранной структуры данных для коллекции. При выборе и разработке алгоритмов методов помимо назначения операций должна учитываться и эффективность алгоритма. Любая задача может быть решена несколькими методами, алгоритмы которых могут отличаться. При выборе алгоритма метода наиболее предпочтительным является алгоритм, который выполняет минимально возможное число действий, т.е. имеет минимальную трудоёмкость.
Трудоёмкость алгоритмов для коллекций, работающих с большими наборами данных, становится очень важной характеристикой. Она напрямую зависит от количества объектов в коллекции n — размера коллекции. Способ измерения n зависит от конкретной структуры данных, на базе которой организована коллекция. Значение n может отражать количество значений в массиве, число элементов связного списка, число узлов дерева поиска, число вершин и рёбер графа и т. п.
Для предварительной оценки трудоёмкости алгоритмов используется нотация «большое О» (Big-O) [3, 6, 8, 9]. Основная идея применения нотации Big-O заключается в том, что необходимо определить, как будет вести себя алгоритм при росте размера коллекции n. Нотация Big-O даёт аппроксимированную верхнюю границу трудоёмкости алгоритма при неограниченном росте n.
Технику получения аналитической оценки Big-O можно продемонстрировать на примере алгоритма сортировки массива методом выбора, содержащего n значений (Таблица 1).
Selection_Sort (A, n)
Число повторений
Источник: studfile.net
Руководство по структурам данных и алгоритмам: введение и настройка среды
Структуры данных — это способ систематической организации данных для эффективного их использования. Различные типы структур данных так или иначе используются почти в каждом корпоративном приложении. Пройдя это руководство, вы получите четкое представление о структурах данных, необходимое для понимания сложности приложений корпоративного уровня.
Базовыми для структуры данных являются следующие термины:
- Интерфейс — это набор поддерживаемых структурой данных операций. Он есть у каждой структуры данных. Интерфейс предоставляет только список поддерживаемых операций, тип принимаемых ими параметров, а также возвращаемый тип этих операций.
- Реализация — она обеспечивает внутреннее представление структуры данных, а также определение алгоритмов, используемых в операциях структуры данных.
Зачем изучать структуры данных и алгоритмы?
С ростом объема данных и сложности современных приложений связаны три основные проблемы:
- Поиск данных. Допустим, нам надо провести инвентаризацию 1 миллиона (1⁰⁶) элементов в хранилище. Если доверить ее приложению, с каждым разом поиск элемента среди такого их количества будет все медленнее, ведь объем данных растет.
- Скорость процессора, хотя и очень высокая, с ростом данных до миллиарда записей оказывается ограниченной.
- Множественные запросы. Если тысячи пользователей будут одновременно искать данные, даже быстрый веб-сервер выйдет из строя.
Решить эти проблемы помогают структуры данных, которые организованы так, что поиск по всем элементам не требуется, а нужные данные находятся почти мгновенно.
С помощью структур данных программно решаются следующие задачи:
- последовательность чисел Фибоначчи;
- задача о ранце;
- ханойская башня;
- поиск кратчайшего пути между всеми парами вершин (алгоритм Флойда-Уоршелла);
- поиск кратчайших путей от одной из вершин графа до всех остальных (алгоритм Дейкстры);
- планирование проектов.
Характеристики структуры данных
- Корректность. Интерфейс структуры данных должен реализовываться корректно.
- Временная сложность. Время выполнения операций структуры данных должно быть как можно меньшим.
- Пространственная сложность. Использование памяти при выполнении операции структуры данных должно быть как можно меньшим.
Случаи времени выполнения
Для сравнения времени выполнения различных структур данных обычно используется три случая:
- Наихудший случай — это сценарий, при котором конкретная операция структуры данных занимает максимально возможное время. Если время операции в наихудшем случае равно ƒ(n), то эта операция займет не более ƒ(n) времени, где ƒ(n) — это функция от n.
- Средний случай — это сценарий, описывающий среднее время выполнения операции структуры данных. Если на выполнение операции уходит ƒ(n) времени, то на m операций уйдет mƒ(n) времени.
- Наилучший случай — это сценарий, описывающий минимально возможное время выполнения операции структуры данных. Если на выполнение операции требуется ƒ(n) времени, то фактическая операция может потребовать время, обозначаемое случайным числом, которое будет максимальным в качестве ƒ(n).
Применение структур данных и алгоритмов
Алгоритм — это пошаговая процедура, которая определяет набор выполняемых в том или ином порядке инструкций для получения желаемого результата. Алгоритмы обычно создаются независимо от базовых языков программирования, т. е. с возможностью реализации на нескольких языках.
С точки зрения структур данных, важны следующие категории алгоритмов:
- Алгоритм поиска элемента в структуре данных.
- Алгоритм сортировки элементов в определенном порядке.
- Алгоритм вставки элемента в структуру данных.
- Алгоритм изменения имеющегося в структуре данных элемента.
- Алгоритм удаления элемента из структуры данных.
Базовая терминология
- Данные — это значения или набор значений.
- Элемент данных — это одиночная единица значений.
- Групповые элементы — это элементы данных, разделенные на подэлементы, называемые групповыми.
- Простейшие элементы — это неделимые элементы данных, которые называются примитивными.
- Атрибут и сущность. Сущность — это то, что содержит определенные атрибуты или свойства, которым могут быть присвоены значения.
- Набор сущностей — это сущности со схожими атрибутами.
- Поле — это одиночная элементарная единица информации, представляющая собой атрибут сущности.
- Запись — это набор значений полей сущности.
- Файл — это совокупность записей сущностей в наборе сущностей.
Необходимые условия
Прежде чем приступать к изучению серии руководства, нужно иметь базовое представление о языке программирования C, текстовом редакторе, выполнении программ и т. д.
Настройка локальной среды
Уже готовы настроить среду для языка программирования C? Тогда вам понадобятся следующие два инструмента: 1. текстовый редактор и 2. компилятор C.
Текстовый редактор
В текстовом редакторе (например, Windows Notepad, OS Edit command, Brief, Epsilon, EMACS, Vim или Vi) будет набираться программа.
Название и версия текстового редактора в разных операционных системах могут различаться. Так, Notepad используется на Windows, а Vim или Vi — на Windows и UNIX.
Файлы, создаваемые с помощью редактора, называются исходными файлами и содержат исходный код программы. Исходные файлы программ на языке С обычно имеют в названии расширение .c .
Чтобы начать программировать, кроме текстового редактора, у вас должно быть достаточно опыта для написания компьютерной программы, сохранения ее в файле, компилирования и выполнения.
Компилятор C
Написанный в исходном файле исходный код является удобным для восприятия человека источником программы. Его нужно скомпилировать, перевести на машинный язык, чтобы процессор мог выполнить программу в соответствии с заданными инструкциями.
Для компиляции исходного кода в конечную исполняемую программу будет использоваться компилятор языка программирования C. Предполагается, что у вас есть о нем базовые знания.
Самый используемый и доступный компилятор — GNU C/C++. Альтернативный вариант — компиляторы от HP или Solaris, если у вас есть соответствующая операционная система (ОС).
А теперь приступим к установке компилятора GNU C/C++ на различные ОС. C и C++ указаны вместе не случайно, ведь компилятор GNU GCC работает на обоих языках программирования.
Установка на UNIX/Linux
Используете ОС UNIX? Тогда проверьте, установлен ли GCC у вас на компьютере, введя в командной строке:
$ gcc -v
Если компилятор GNU уже установлен, должно появиться похожее сообщение:
Using built-in specs.
Target: i386-redhat-linux
Configured with: ../configure —prefix = /usr .
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-46)
Если же нет, придется установить GCC самостоятельно (подробные инструкции доступны здесь на англ. яз: https://gcc.gnu.org/install/).
Установка на Mac OS
Проще всего установить GCC, загрузив среду разработки Xcode с сайта Apple и следуя простым инструкциям по установке. После настройки Xcode вы сможете использовать компилятор GNU для C/C++.
Установка на Windows
Чтобы заполучить GCC на Windows, потребуется установить MinGW. Для этого перейдите на домашнюю страницу MinGW и далее по ссылке на страницу загрузки. Загрузите последнюю версию программы установки MinGW с названием MinGW-.exe.
Обязательный минимум при установке MinWG: gcc-core, gcc-g++, binutils и среда выполнения MinGW — но вы можете не ограничиваться этим и установить что-то еще.
Добавьте подкаталог bin из установки MinGW в переменную среды PATH, чтобы указывать эти инструменты в командной строке по их простым именам.
По завершении установки вы сможете запускать из командной строки Windows gcc, g++, ar, ranlib, dlltool и другие инструменты GNU.
- Deepnote — новая IDE для специалистов по данным
- 5 ловких приемов Xcode для рефакторинга кода
- 5 алгоритмов, которые изменили мир
Источник: nuancesprog.ru