Здравствуйте, я Gauri wankhade,
разработчик программного обеспечения, Бангалор, Индия

В этой статье мы поговорим об основах структур данных и алгоритмов.

Что такое структуры данных и алгоритмы?
Структура данных — это способ организации данных. Алгоритмы — это способ эффективного использования структур данных для решения проблемы.

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

Бывший. Для данного массива индекс находится в диапазоне от 0 до длины массива.

NumArray = [1, 2, 3, 4, 5]
// access element at index 2
elem = NumArray[2]
// elem is 3

Нелинейные структуры данных предназначены для доступа к элементам определенным образом, когда последовательный доступ не подходит. Бывший. Дерево, график, куча и т. д.

Что такое древовидная структура данных?

Ну представьте нормальное дерево вверх ногами

По внешнему виду мы можем сказать, что это не что-то обычное для изучения, например, прогулка по дороге или обход списка элементов. Чтобы исследовать дерево, нам нужно понять его структуру.

Дерево — это структура данных, в которой каждый узел хранит некоторое значение и адрес своего левого и правого узлов. Узел, не имеющий родителя, считается корневым узлом дерева. Здесь узел со значением 1 является корневым узлом, в котором хранятся адреса узла-2 и узла-3.

Основная идея изучения дерева заключается в рассмотрении одного узла за раз и изучении его дочерних узлов (левого и правого узлов).

Методы изучения Дерева

  • Обход предзаказа
  • Обход постпорядка
  • Неупорядоченный обход

обратитесь за более подробной информацией. https://www.educba.com/tree-traversal-in-data-structure/

Что такое график?

Граф — это не что иное, как набор вершин и ребер, соединяющих эти вершины.

Чем Tree отличается от Graph?

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

Одним из важных аспектов Tree and Graph является то, что каждое дерево представляет собой граф без циклов. Если вы удалите все циклы из графика, он создаст дерево.

В приведенном выше примере мы удалили ребро DE, чтобы преобразовать граф в дерево. Такие ребра называются задними ребрами. Наличие заднего края указывает на наличие цикла в графике. Эта идея порождает концепцию остовного дерева.

Что такое связующее дерево?

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

Что такое связующее дерево с минимальной стоимостью?

Мы можем вывести остовное дерево минимальной стоимости для взвешенного графа, это означает, что каждое ребро будет иметь некоторый вес/стоимость. Если сумма стоимости ребер остовного дерева является минимальной из всех возможных остовных деревьев, то говорят, что это остовное дерево с минимальной стоимостью.

Способы поиска MCST

  • Алгоритм Крускала
  • Алгоритм Прима

Анализ алгоритма

Чтобы найти наиболее эффективный подход к решению любой проблемы, должен быть способ измерить существующие подходы и выбрать лучший из них.

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

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

Временная сложность — это количество раз выполнения оператора.

Arr = [4, 3, 2, 7, 8]
// time complexity to find 4 in the Arr is 1
// time complexity to find 8 in the Arr is 5, because length of      // Arr is 5

В приведенном выше примере нам нужно было пройти только один элемент, чтобы найти 4 в массиве. В случае 8 мы прошли весь массив, чтобы найти 8 в конце, что делает временную сложность операции равной 5.

Существует три способа представления временной сложности с использованием асимптотических обозначений.

  • Сложность в лучшем случае (обозначение Омега)
  • Сложность в наихудшем случае (обозначение Big O)
  • Средняя сложность (тета-обозначение)

В заданном списке элементов есть вероятность, что искомый элемент является первым элементом списка. Это в лучшем случае. В худшем случае искомый элемент будет найден последним. Обычно при анализе алгоритмов мы рассматриваем сценарий наихудшего случая (обозначение Big O).

Примеры временной сложности

  1. O(1) постоянная временная сложность

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

2. O(N) Линейная временная сложность

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

3. О(логин)

Чтобы понять сложность O(logn), давайте рассмотрим пример бинарного поиска.

Мы ищем 5 в заданном отсортированном списке элементов.

Arr = [1, 2, 3, 4, 5, 6]
// initially, low is 0 and high is highest index which is length of Arr minus 1
low = 0
high = 6 - 1
mid = (low + high) / 2
mid  = (0 + 5) / 2

проверить, если

  • Arr[mid] равно 5
  • Если да — вернуться в середине
  • If no —
  • Проверьте Arr[mid] ‹ 5. Если да, обновите low = mid + 1
  • В противном случае проверьте Arr[mid] › 5. Если да, обновите high = mid-1

Итак, при использовании бинарного поиска потребовалось две итерации, чтобы найти элемент 5 в заданном списке.

Каково будет количество итераций, если мы просто проверим каждый элемент, чтобы найти 5? Поскольку 5 является 5-м элементом списка, для поиска элемента потребуется 5 итераций.

В бинарном поиске мы продолжаем делить массив пополам. Исходя из условий, мы решаем, какую половину рассматривать, пока не найдем нужный элемент. Это делает временную сложность операции O (logN), где N — количество элементов в массиве.

For Array of length N = 8
O(logN) = O(log8)
we can say, 8 = 2 * 2 * 2
i.e 8 = 2^3
O(logN) = O(2^3)
O(logN) = 3 * O(2)

Из приведенной выше иллюстрации мы можем предположить, что временная сложность поиска элемента в заданном массиве длиной 8 равна 3. Это означает, что массив будет продолжать уменьшаться до половины до трех итераций.

Делитесь и ставьте лайк, если статья оказалась полезной. Следите за мной на канале Gauri wankhade и в Твиттере gauri_infj.

Спасибо!!!

Счастливого обучения…