Алгоритмы, Структуры данных. Коллекции. Урок №4

1.

Алгоритмы, Структуры данных.
Коллекции
УРОК: № 4

2.

Алгоритм — это четкая последовательность действий,
выполнение которой дает какой-то заранее
известный результат. Проще говоря, это набор
инструкций для конкретной задачи
УРОК: № 4

3.

Дискретность. Алгоритм — не единая неделимая структура, он состоит из
отдельных маленьких шагов, или действий. Эти действия идут в определенном
порядке, одно начинается после завершения другого.
Результативность. Выполнение алгоритма должно привести к какому-либо
результату и не оставлять неопределенности. Результат может в том числе
оказаться неудачным — например, алгоритм может сообщить, что решения
нет, — но он должен быть.
Детерминированность. На каждом шаге не должно возникать разночтений и
разногласий, инструкции должны быть четко определены.
УРОК: № 4
СВОЙСТВА АЛГОРИТМОВ

4.

Массовость. Алгоритм обычно можно экстраполировать на похожие задачи с
другими исходными данными — достаточно поменять изначальные условия.
Например, стандартный алгоритм по решению квадратного уравнения
останется неизменным вне зависимости от того, какие числа будут
использоваться в этом уравнении.
Понятность. Алгоритм должен включать только действия, известные и понятные
исполнителю.
Конечность. Алгоритмы конечны, они должны завершаться и выдавать
результат, в некоторых определениях — за заранее известное число шагов.
УРОК: № 4
СВОЙСТВА АЛГОРИТМОВ

5.

Линейные. Это самый простой тип алгоритма: действия идут друг за другом,
каждое начинается после того, как закончится предыдущее. Они не
переставляются местами, не повторяются, выполняются при любых условиях.
Ветвящиеся. В этом типе алгоритма появляется ветвление: какие-то действия
выполняются, только если верны некоторые условия. Например, если число
меньше нуля, то его нужно удалить из структуры данных. Можно добавлять и
вторую ветку: что делать, если условие неверно — например, число больше
нуля или равно ему. Условий может быть несколько, они могут
комбинироваться друг с другом.
УРОК: № 4
ВИДЫ АЛГОРИТМОВ

6.

Циклические. Такие алгоритмы выполняются в цикле. Когда какой-то блок
действий заканчивается, эти действия начинаются снова и повторяются
некоторое количество раз. Цикл может включать в себя одно действие или
последовательность, а количество повторений может быть фиксированным или
зависеть от условия: например, повторять этот блок кода, пока в структуре
данных не останется пустых ячеек. В некоторых случаях цикл может быть
бесконечным.
Рекурсивные. Рекурсия — это явление, когда какой-то алгоритм вызывает сам
себя, но с другими входными данными. Это не цикл: данные другие, но
«экземпляров» работающих программ несколько, а не одна. Известный
пример рекурсивного алгоритма — расчет чисел Фибоначчи.
Рекурсия позволяет изящно решать некоторые задачи, но с ней надо быть
осторожнее: такие алгоритмы могут сильно нагружать ресурсы системы и
работать медленнее других.
УРОК: № 4
ВИДЫ АЛГОРИТМОВ

7.

Вероятностные. Такие алгоритмы упоминаются реже, но это довольно
интересный тип: работа алгоритма зависит не только от входных данных, но и
от случайных величин. К ним, например, относятся известные алгоритмы ЛасВегас и Монте-Карло.
Основные и вспомогательные. Это еще один вид классификации. Основной
алгоритм решает непосредственную задачу, вспомогательный решает
подзадачу и может использоваться внутри основного — для этого там просто
указываются его название и входные данные. Пример вспомогательного
алгоритма — любая программная функция.
УРОК: № 4
ВИДЫ АЛГОРИТМОВ

8.

Понятие «сложность» — одно из ключевых в изучении алгоритмов.
Оно означает не то, насколько трудно понять тот или иной метод,
а ресурсы, затраченные на вычисление. Если сложность высокая,
алгоритм будет выполняться медленнее и, возможно, тратить
больше аппаратных ресурсов; такого желательно избегать.
Сложность обычно описывают большой буквой O. После нее в
скобках указывается значение, от которого зависит время
выполнения. Это обозначение из математики, которое описывает
поведение разных функций.
УРОК: № 4
СЛОЖНОСТЬ АЛГОРИТМА

9.

O(1) означает, что алгоритм выполняется за фиксированное
константное время. Это самые эффективные алгоритмы.
Пример 1)
Пример 2)
УРОК: № 4
СЛОЖНОСТЬ АЛГОРИТМА

10.

O(n) — это сложность линейных алгоритмов. n здесь и дальше
обозначает размер входных данных: чем больше n, тем дольше
выполняется алгоритм.
УРОК: № 4
СЛОЖНОСТЬ АЛГОРИТМА

11.

O(n²) тоже означает, что чем больше n, тем выше сложность. Но
зависимость тут не линейная, а квадратичная, то есть скорость
возрастает намного быстрее. Это неэффективные алгоритмы,
например с вложенными циклами.
УРОК: № 4
СЛОЖНОСТЬ АЛГОРИТМА

12.

O(log n) — более эффективный алгоритм. Скорость его
выполнения рассчитывается логарифмически, то есть зависит от
логарифма n.
УРОК: № 4
СЛОЖНОСТЬ АЛГОРИТМА

13.

O(√n) — алгоритм, скорость которого зависит от
квадратного корня из n. Он менее эффективен, чем
логарифмический, но эффективнее линейного.
Существуют также O(n³), O(n + n) и другие
малоэффективные алгоритмы с высокими степенями.
Их сложность растет очень быстро, и их лучше не
использовать.
УРОК: № 4
СЛОЖНОСТЬ АЛГОРИТМА

14.

Generics — или же обобщения, это обобщенные типы и методы,
которые помогают нам уйти от строгой привязки к типу данных.
Используются в качестве некой абстракции и индикатора того, что наш
функционал может работать с различными типами данных.
Очень часто дженерики используют вместе с наследованием, чтобы
определить конкретные свойства обобщенного типа данных.
УРОК: № 4
GENERICS

15.

Структура данных — это способ организации информации для более
эффективного использования. В программировании структурой обычно
называют набор данных, связанных определённым образом. Например,
массив — это структура.
Со структурой можно работать: добавлять данные, извлекать их и
обрабатывать, например изменять, анализировать, сортировать. Для каждой
структуры данных — свои алгоритмы. Работа программиста — правильно
выбирать уже написанные готовые либо писать свои.
Главное свойство структур данных в том, что у любой единицы данных должно
быть чёткое место, по которому её можно найти. Как определяется это место и
как происходит поиск, зависит от конкретной структуры.
УРОК: № 4
СТРУКТУРА ДАННЫХ

16.

УРОК: № 4
СТРУКТУРА ДАННЫХ

17.

УРОК: № 4
СТРУКТУРА ДАННЫХ

18.

Коллекции — это общее название нескольких структур данных,
используемых в Java. Это первый Framework с которым мы
познакомимся.
Созданы для удобства и оптимизации хранения и обработки
информации.
УРОК: № 4
КОЛЛЕКЦИИ

19.

УРОК: № 4
ИЕРАРХИЯ КОЛЛЕКЦИЙ

20.

Интерфейс Iterable в Java используется для обеспечения возможности
итерирования (перебора) элементов коллекции. Он определяет единственный
метод iterator(), который возвращает объект Iterator.
Iterator является еще одним интерфейсом, который определяет методы для
последовательного доступа к элементам коллекции. Он используется для
выполнения итераций по элементам коллекции и предоставляет методы, такие
как next(), hasNext() и remove().
Iterable — базовый интерфейс для коллекций. Содержит в себе:
1) Итератор, который отвечает за переход к следующему элементу коллекции.
2) Метод forEach(), который обязывает коллекции реализовать проход по всем
элементам коллекции.
3) Spliterator — интерфейс используемый для правильного описания
многопоточности, но об этом позже.
УРОК: № 4 ИНТЕРФЕЙС ITERABLE

21.

Collection — Интерфейс Collection в Java является базовым
интерфейсом для структур данных, представляющих группу объектов,
называемых элементами. Он предоставляет основные операции для
работы с коллекцией объектов.
1) size() - вернуть количество элементов в коллекции.
2) contains() - вернуть, содержится ли элемент в коллекции.
3) toArray() - преобразовать коллекцию в массив.
4) add() - добавить элемент в коллекцию.
5) remove() - удалить элемент из коллекции.
6) containsAll() - проверить, содержатся ли элементы одной коллекции в
другой.
7) addAll() - добавить элементы одной коллекции в другую.
8) removeAll() - удалить элементы содержащиеся в одной коллекции из
другой.
УРОК: № 4 ИНТЕРФЕЙС COLLECTION

22.

Интерфейс Collection реализуют в себе 4 интерфейса:
1) List<> - упорядоченный список, гарантирует порядок добавления
элементов и допускает дубликаты.
2) Set<> - неупорядоченное множество элементов, не гарантирует
порядок добавления, но и не допускает дубликаты.
3) Queue<> - очередь, реализует принцип FIFO(first in — first out),
гарантирует порядок добавления и допускает дубликаты.
4) Deque<> - та же очередь, но позволяет добавлять элементы как в
начало списка, так и в конец. Часто используется для реализации
структуры Stack, работающей по принципу LIFO(last in — first out).
УРОК: № 4 ИНТЕРФЕЙС COLLECTION

23.

Интерфейс List<> добавляет к методам коллекции, методы:
1) indexOf() - метод, который возвращает первый индекс, на котором
находится элемент.
2) get() - метод, возвращающий значение по индексу.
3) set() - метод, который устанавливает новое значение по индексу.
4) add() - метод, добавляющий новое значение в существующий индекс.
5) remove() - метод удаляющий значение по индексу.
6) lastIndexOf() - метод, возвращающий последний индекс, по которому
находится элемент.
УРОК: № 4 ИНТЕРФЕЙС LIST

24.

Интерфейс List<> имеет 2 основные реализации:
1) ArrayList<> - список, который хранит в себе данные в виде обычного
массива.
2) LinkedList<> - список, который хранит данные в виде значения и
указателей на предыдущий и следующий элементы в списке.
Если наш List<> используется больше для получения данных по
индексу, стоит использовать ArrayList<>, но если наш список
используется больше для вставки и удаления данных, то лучше
использовать LinkedList<>.
УРОК: № 4 ИНТЕРФЕЙС LIST

25.

Интерфейс Set<> ничего не добавляет к методам Collection. Он лишь
гарантирует отсутствие дубликатов в множестве значений. Реализации
этого интерфейса работают также как и реализации интерфейса Map,
за одним исключением: в случае Set<> значения и являются ключами,
а в поле значения записывается объект пустышка(new Object()).
Этим и достигается уникальность значений в множестве.
У интерфейса Set<> есть 2 основные реализации:
1) HashSet<> - базовая реализация, использующая HashMap для
хранения данных.
2)
LinkedHashSet<> - то же самое, что и HashSet, только
гарантирует порядок элементов при добавлении.
УРОК: № 4 ИНТЕРФЕЙС SET

26.

Интерфейс Queue<> добавляет следующие методы:
1) offer() - безопасное добавление элемента в очередь.
2) remove() - удаление элемента из очереди, возможно удалить элемент
на любом месте.
3) poll() - удаление первого элемента из очереди.
4) element() - получение первого элемента в списке.
5) peek() - делает то же самое что и element(), но в более «мягком»
стиле.
Интерфейс Deque<> по своей сути такой же, как и Queue<>, но
позволяет все действия и с обратной стороны.
УРОК: № 4 ИНТЕРФЕЙС QUEUE

27.

Map — интерфейс, представляющий данные в виде «Ключ — Значение».
Не наследует интефейсы Iterable и Collection, ввиду того, что использует
понятия «Ключ(key)» и «Значение(value)». Если представлять это в
понятиях массива, то храниться будет value, но вместо индекса будет
key.
Интерфейс Map имеет 3 основные реализации:
1) HashMap — реализация, которая хранит ключи в виде hashCode() с
обособленной hash-функцией.
2) LinkedHashMap — реализация, унаследованная от HashMap, но
гарантирующая порядок элементов в коллекции.
3) TreeMap — реализация, хранящая данные в виде красно-черного
дерева. Эту реализацию можно будет изучить будучи более опытным
разработчиком.
УРОК: № 4 ИНТЕРФЕЙС MAP

28.

УРОК: № 4 ВРЕМЕННАЯ СЛОЖНОСТЬ
РАБОТЫ С КОЛЛЕКЦИЯМИ