Итак, DSA, верно?
Абсолютно, почему бы и нет. Давайте будем честными, DSA — это то, что каждый немного боится изучать. DSA — это одна из таких вещей в колледже или на любой технической работе, если уж на то пошло, без этого предмета ничего нельзя было бы сделать. Каждое собеседование, независимо от портфолио, на которое вы претендуете, требует абсолютного понимания концепций DSA.
Как следует из названия, данные — это то, о чем идет речь. То, как данные структурированы в каждом аспекте, является концепцией всего предмета, а алгоритмы — это методы, которые мы разработали для упрощения структур данных.
Итак, я тоже сейчас учусь на втором курсе, стремясь получить высокооплачиваемую работу в сфере технологий, и я очень боюсь этого предмета, и, честно говоря, это даже не так интересно. Эта статья также является своего рода мотивацией для меня, чтобы встать, полюбить предмет (потому что это все данные, а я люблю играться с данными) и попытаться как можно лучше справиться с этим. Эта статья послужит обзором моих теоретических знаний о DSA, и мы увидим, к чему приведет нас эта тема в ближайшем будущем, когда я буду готовиться к размещению.
Хорошо продуманная структура данных и эффективный алгоритм могут превратить вычислительный кошмар в гладкое и элегантное решение.
Структуры данных и алгоритмы могут быть реализованы на любом языке по вашему выбору, python, java, c, c++ и т. д.
Теперь, что такое структура данных?
Краткий ответ таков: структура данных — это особое средство организации данных в системе для доступа и использования.
Длинный ответ заключается в том, что структура данных представляет собой смесь организации данных, управления, поиска и хранения, объединенных в один формат, обеспечивающий эффективный доступ и модификацию. Это сбор значений данных, отношений, которые они разделяют, и применимых функций или операций.
Вот реальный пример. Если вы пойдете в библиотеку и захотите найти книгу по военной истории 20-го века, вы пойдете в раздел «История». Оттуда вы найдете специально отведенное место для военной истории, а затем просмотрите книги, отсортированные в хронологическом порядке, пока не найдете 20-й век. Теперь считайте книги своими данными, а библиотечный метод сортировки книг — структурой данных, и все готово!
Структуры данных необходимы для управления огромными объемами генерируемых данных и являются критическим фактором повышения эффективности алгоритмов.
Типы структуры данных
Линейная структура данных
Нелинейная структура данных
Линейные структуры данных
В линейных структурах данных элементы располагаются последовательно друг за другом. Поскольку элементы расположены в определенном порядке, их легко реализовать.
1. Массив
В массиве элементы в памяти располагаются в непрерывной памяти. Все элементы массива относятся к одному типу. А тип элементов, которые можно хранить в виде массивов, определяется языком программирования.
2. Стек
В структуре данных стека элементы хранятся по принципу LIFO. То есть последний элемент, сохраненный в стеке, будет удален первым.
Это работает так же, как стопка тарелок, где последняя тарелка, оставшаяся в стопке, будет удалена первой.
3. Очередь
В отличие от стека, структура данных очереди работает по принципу FIFO, где первый элемент, хранящийся в очереди, будет удален первым.
Это работает так же, как очередь людей в кассе, где первый человек в очереди получит билет первым.
4. Связанный список
В структуре данных связанного списка элементы данных связаны через ряд узлов. И каждый узел содержит элементы данных и адрес к следующему узлу.
Нелинейные структуры данных
В отличие от линейных структур данных, элементы в нелинейных структурах данных не расположены в какой-либо последовательности. Вместо этого они расположены иерархически, где один элемент будет связан с одним или несколькими элементами.
Нелинейные структуры данных далее делятся на структуры данных на основе графа и дерева.
1. График
В структуре данных графа каждый узел называется вершиной, и каждая вершина связана с другими вершинами через ребра.
2. Структура данных деревьев
Подобно графу, дерево также представляет собой набор вершин и ребер. Однако в древовидной структуре данных между двумя вершинами может быть только одно ребро.
Линейные и нелинейные структуры данных
Типы графиков
- Нулевой график
- Тривиальный график
- Неориентированный граф
- Направленный граф
- Подключенный график
- Отключенный график
- Обычный график
- Полный график
- График цикла
- Циклический график
- Ациклический график
- Конечный граф
- Бесконечный график
- Двудольный граф
- Планарный график
- Простой график
- Мульти график
- Псевдограф
- График Эйлера
- Гамильтонов график
Обход графа в структуре данных
Обход графа — это посещение или обновление каждой вершины графа. Порядок, в котором они посещают вершины, классифицирует обходы. Существует два способа реализации обхода графа:
- Поиск в ширину (BFS). Это операция обхода, которая проходит по графику по горизонтали. Он проходит через все узлы на одном уровне, прежде чем перейти на следующий уровень. Он начинается в корне графа и проходит через все узлы на одном уровне глубины, прежде чем перейти к следующему уровню.
- Поиск в глубину (DFS): это еще одна операция обхода, которая перемещает график по вертикали. Он начинается с корневого узла графа и исследует каждую ветвь, насколько это возможно, перед возвратом.
Следующие типы древовидной структуры данных:
- Общее дерево:
- Двоичное дерево поиска
- Дерево AVL
- Красно-черное дерево
- Показать дерево
- Трава
- B-дерево
- Минимальное связующее дерево
Теперь давайте узнаем о различных алгоритмах.
Но сначала, что такое алгоритмы в области компьютерных наук?
Алгоритм — это процедура, используемая для решения проблемы или выполнения вычислений. Алгоритмы действуют как точный список инструкций, которые шаг за шагом выполняют определенные действия в аппаратных или программных процедурах.
Алгоритмы широко используются во всех областях ИТ. В математике и информатике алгоритм обычно относится к небольшой процедуре, которая решает повторяющуюся проблему. Алгоритмы также используются в качестве спецификаций для выполнения обработки данных и играют важную роль в автоматизированных системах.
Алгоритм можно использовать для сортировки наборов чисел или для более сложных задач, таких как рекомендация пользовательского контента в социальных сетях. Алгоритмы обычно начинаются с начального ввода и инструкций, описывающих конкретное вычисление. Когда вычисление выполнено, процесс выдает результат.
Типы алгоритмов:
Идет поиск:
1) Бинарный поиск
2) Линейный поиск
3) Поиск в глубину
4) Поиск в ширину
Сортировка:
1) Сортировка вставками
2) Сортировка кучей
3) Сортировка выбором
4) Сортировка слиянием
5) Быстрая сортировка
6) Сортировка подсчетом
7) Сортировка ведром
8) Пузырьковая сортировка
9) Сортировка по основанию
10) Сортировка ракушки
Графики:
1) Алгоритм Крускала
2) Алгоритм Дейкстры
3) Алгоритм Беллмана Форда
4) Алгоритм Флойда Уоршалла
5) Алгоритм топологической сортировки
6) Алгоритм заливки
7) Алгоритм Прима
Массивы:
1) Алгоритм Кадане
2) Алгоритм обнаружения цикла Флойда
Дерево:
1) Дерево АА
2) Двоичное индексированное дерево или дерево Фенвика
5) Дерево кучи
Другие:
1) Алгоритм сжатия кода Хаффмана
2) Алгоритм Евклида
3) Алгоритм хэш-карты
4) Динамическое программирование
5) Жадные алгоритмы
6) Алгоритмы «разделяй и властвуй»
Заключение
Итак, обо всем по порядку. В этой статье я не стал подробно рассказывать о каждой структуре данных и алгоритме. О DSA можно написать еще тонны и тысячи вещей. Каждый алгоритм имеет свой собственный набор математических и программных средств, аналитическую часть, с несколькими обозначениями, с некоторым набором очень распространенных примеров, одним из которых является задача о рюкзаке. Этот предмет называется DAA, алгоритм проектирования и анализ, который объединяет некоторые фундаментальные темы, такие как сложность времени и пространства, но это тема для другого дня. Тем не менее, я прилагаю список хороших вопросов от POV размещения. Вы можете проверить это здесь.
Цель статьи состояла в том, чтобы дать краткое и быстрое понимание того, что такое DSA на низовом уровне. С этим давайте начнем наш путь к успеху в DSA, и давайте заставим себя гордиться, и поверьте мне, тому, кто может решить сложные проблемы DSA, я имею в виду, что это настоящая гибкость в мире технологий.
До следующего раза, продолжайте работать, продолжайте учиться!!!
