DataStructure And Algo
1.0.0
Структуры данных являются специализированным средством организации и хранения данных в компьютерах таким образом, что мы можем более эффективно выполнять операции на хранимых данных. Структуры данных имеют широкий и разнообразный объем использования в области компьютерной науки и разработки программного обеспечения. Структуры данных используются практически в каждой программе или программной системе, которая была разработана. Более того, структуры данных находятся под основы информатики и разработки программного обеспечения. Это ключевая тема, когда речь идет о вопросах интервью для разработки программного обеспечения. Следовательно, как разработчики, мы должны иметь хорошие знания о структурах данных.
Массив - это структура фиксированного размера, которая может удерживать элементы того же типа данных. Это может быть множество целых чисел, массив чисел с плавающей точкой, массив струн или даже массив массивов (например, 2-мерные массивы). Массивы индексируются, а это означает, что возможный случайный доступ.
Вставка элементов в массив и удаление элементов из массива не может быть сделано сразу, поскольку массивы фиксируются по размеру. Если вы хотите вставить элемент в массив, сначала вам придется создать новый массив с увеличением размера (размер текущего + 1), скопируйте существующие элементы и добавьте новый элемент. То же самое касается удаления с новым массивом уменьшенного размера.
Связанный список - это последовательная структура, которая состоит из последовательности элементов в линейном порядке, которые связаны друг с другом. Следовательно, вы должны получить доступ к данным последовательно, и случайный доступ невозможно. Связанные списки обеспечивают простое и гибкое представление динамических наборов.
Стек - это LIFO (последнее в первом выходе - вначале можно получить структуру, расположенную наконец, можно получить), которая обычно можно найти во многих языках программирования. Эта структура называется «стеком», потому что она напоминает реальную стек-стопку пластин.
Используется для оценки экспрессии (например: алгоритм шунтирующего двора для анализа и оценки математических выражений). Используется для реализации вызовов функций в программировании рекурсии.
Очередь представляет собой FIFO (сначала сначала в первую очередь - сначала можно получить структуру, помещенную сначала), которая может быть обычно встречается во многих языках программирования. Эта структура называется «очередью», потому что она напоминает очередь в реальном мире-людей, ожидающих в очереди.
Используется для управления потоками в многопользовании. Используется для реализации систем очередей (например: приоритетные очереди).
Хэш -таблица - это структура данных, которая хранит значения, которые имеют ключи, связанные с каждым из них. Кроме того, он поддерживает поиск эффективно, если мы знаем ключ, связанный со значением. Следовательно, очень эффективно вставить и поиск, независимо от размера данных.
Прямая адресация использует отображение один к одному между значениями и ключами при хранении в таблице. Тем не менее, существует проблема с таким подходом, когда существует большое количество пар ключей. Таблица будет огромной с таким большим количеством записей и может быть нецелесообразно или даже невозможно хранить, учитывая память, доступную на типичном компьютере. Чтобы избежать этой проблемы, мы используем хэш -таблицы .
Специальная функция с именем функции хэш (h) используется для преодоления вышеупомянутой проблемы при прямом решении. В прямом доступе значение с ключом K хранится в слоте k. Используя функцию хеш, мы рассчитываем индекс таблицы (слот), к которому идет каждое значение. Значение, рассчитанное с использованием хэш -функции для данного ключа, называется значением хэша, которое указывает индекс таблицы, с которой значение отображается.
Дерево - это иерархическая структура, где данные организованы иерархически и связаны вместе. Эта структура отличается от связанного списка, тогда как в связанном списке элементы связаны в линейном порядке. Различные типы деревьев были разработаны в течение последних десятилетий, чтобы удовлетворить определенные применения и соответствовать определенным ограничениям. Некоторые примеры-бинарное поисковое дерево, B дерево, треп, красное черное дерево, дерево Splay, Avl Tree и N-Ary Tree.
Дерево бинарного поиска (BST), как следует из названия, представляет собой двоичное дерево, где данные организованы в иерархической структуре. Эта структура данных сохраняет значения в отсортированном порядке. Каждый узел в двоичном дереве поиска состоит из следующих атрибутов.
Дерево бинарного поиска демонстрирует уникальное свойство, которое отличает его от других деревьев. Это свойство известно как свойство бинарного и-исследовательского дерева **.
Куча - это особый случай бинарного дерева, где родительские узлы сравниваются с их детьми с их ценностями и расположены соответствующим образом.
Куча может быть 2 типа.
График состоит из конечного набора вершин или узлов и набора краев , соединяющих эти вершины.
Порядок графика - это количество вершин на графике. Размер графа - это количество краев на графике.
Говорят, что два узла являются смежными , если они связаны друг с другом одним и тем же краем.
График g, как говорят, является направленным графом, если все его края имеют направление, указывающее, что такое начальная вершина и какова конечная вершина . Мы говорим, что (u, v) является инцидентом или оставляет вершину U и инцидент или входит в Vertex v. Self-Coups: края от вершины к себе.
Говорят, что график G является неориентированным графом, если все его края не имеют направления. Это может идти в обоих отношениях между двумя вершинами.
Если вершина не подключена к каким -либо другим узлам на графике, говорят, что она изолирована .
Trie -это дерево, похожая на деревья, структуру данных поиска информации, узлы которых хранят буквы алфавита. Он также известен как цифровое дерево, дерево радиосвяза или дерево префикса.
Trie - это эффективная структура данных поиска информации. Используя TRIE, сложности поиска могут быть доведены до оптимального предела (длина ключа). Если мы храним ключи в двоичном дереве поиска, хорошо сбалансированному BST BST потребуется время, пропорционально m * log n, где m - максимальная длина струны, а N - количество ключей в дереве. Используя Trie, мы можем искать ключ во время O (M) .
1. Стандартный Три : это упорядоченная структура данных, как структура данных.
2. Сжатый Trie : он используется для достижения пространственной оптимизации. Сжатая Trie - это расширенная версия стандартного Trie.
3. Суффикс Trie : суффикс Trie - это расширенная версия сжатого Trie.
С Trie мы можем вставить и найти строки во время O (l), где L представляет длину одного слова. Это, очевидно, быстрее, чем BST. Это также быстрее, чем хэшинг из -за того, как он реализован. Нам не нужно вычислять какую -либо хэш -функцию. Еще одно преимущество Trie, мы можем легко распечатать все слова в алфавитном порядке, что нелегко возможно с хэшином.
Динамическое программирование -это метод, который разбивает проблемы на подпроблемы и экономит результат для будущих целей, чтобы нам не нужно было снова вычислять результат. Подзадачи оптимизированы для оптимизации общего решения, известного как оптимальное свойство субструктуры. Основное использование динамического программирования заключается в решении задач оптимизации. Здесь проблемы с оптимизацией означают, что когда мы пытаемся выяснить минимум или максимальное решение проблемы. Динамическое программирование гарантирует найти оптимальное решение проблемы, если решение существует.
Алгоритм сложности временной сложности o (1) Посмотреть конкретный элемент в массиве, например, это, например: print (my_array [97]). Независимо от размера массива, элемент можно найти непосредственно, это требует просто одной операции. (Кстати, это не алгоритм, но он может помочь нам понять, как работает сложность времени.)
O (n) Нахождение наименьшего значения. Алгоритм должен выполнять n операций в массиве со значениями n, чтобы найти самое низкое значение, поскольку алгоритм должен сравнивать каждое значение один раз.
O (N 2) Сорта пузырьков, сортировка выбора и сортировка вставки - это алгоритмы со сложностью времени. Причина их временных сложностей объясняется на страницах этих алгоритмов.
Большие наборы данных значительно замедляют эти алгоритмы. С увеличением числа N с 100 до 200 значений, количество операций может увеличиться на 30000!
O (n log n) алгоритм QuickSort в среднем более быстрее, чем три алгоритма сортировки, упомянутые выше, причем O (n log n) является средним, а не худшим временем. В худшем случае для QuickSort также o (n 2), но это среднее время, которое делает QuickSort таким интересным. Позже мы узнаем о QuickSort.
Ссылка взята по этой ссылке - Sourav Saini?
