Структуры данных и алгоритмы - обзор

Структура данных - это систематический способ организации данных с целью их эффективного использования. Следующие термины являются базовыми терминами структуры данных.

  • Интерфейс - каждая структура данных имеет интерфейс. Интерфейс представляет собой набор операций, которые поддерживает структура данных. Интерфейс предоставляет только список поддерживаемых операций, тип параметров, которые они могут принять, и возвращает тип этих операций.

  • Реализация - Реализация обеспечивает внутреннее представление структуры данных. Реализация также обеспечивает определение алгоритмов, используемых в операциях структуры данных.

Характеристики структуры данных

  • Корректность - реализация структуры данных должна правильно реализовывать свой интерфейс.

  • Сложность времени - время выполнения или время выполнения операций структуры данных должно быть как можно меньше.

  • Сложность пространства - использование памяти операцией структуры данных должно быть как можно меньше.

Потребность в структуре данных

Поскольку приложения становятся сложными и богатыми данными, есть три общие проблемы, с которыми приложения сталкиваются в настоящее время.

  • Поиск данных - Рассмотрите инвентарь 1 миллиона (10 6 ) предметов магазина. Если приложение должно искать элемент, оно должно искать элемент в 1 миллионе (10 6 ) элементов каждый раз, замедляя поиск. По мере роста данных поиск будет замедляться.

  • Скорость процессора. Скорость процессора, хотя и очень высокая, ограничивается, если объем данных увеличивается до миллиарда записей.

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

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

Случаи выполнения

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

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

  • Средний случай - это сценарий, отображающий среднее время выполнения операции структуры данных. Если на выполнение операции уходит ƒ (n) времени, то m операций займет время mƒ (n).

  • Наилучший случай - это сценарий, отображающий наименьшее возможное время выполнения операции структуры данных. Если на выполнение операции уходит ƒ (n) времени, то фактическая операция может занять время как случайное число, которое будет максимальным как ƒ (n).

Основная терминология

  • Данные - данные являются значениями или набором значений.

  • Элемент данных - элемент данных относится к одной единице значений.

  • Элементы группы - элементы данных, которые разделены на подэлементы, называются элементами группы.

  • Элементарные элементы - элементы данных, которые нельзя разделить, называются элементарными элементами.

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

  • Entity Set - Объекты с похожими атрибутами образуют набор объектов .

  • Поле - Поле - это единая элементарная единица информации, представляющая атрибут сущности.

  • Запись - Запись - это коллекция значений полей данного объекта.

  • Файл - Файл представляет собой набор записей сущностей в данном наборе сущностей.