Структуры данных и алгоритмы - Обзор
Структура данных - это систематический способ организации данных для их эффективного использования. Следующие термины являются основными терминами структуры данных.
Interface- Каждая структура данных имеет интерфейс. Интерфейс представляет собой набор операций, поддерживаемых структурой данных. Интерфейс предоставляет только список поддерживаемых операций, тип параметров, которые они могут принимать, и тип возвращаемого значения этих операций.
Implementation- Реализация обеспечивает внутреннее представление структуры данных. Реализация также обеспечивает определение алгоритмов, используемых в операциях со структурой данных.
Характеристики структуры данных
Correctness - Реализация структуры данных должна правильно реализовывать ее интерфейс.
Time Complexity - Время выполнения или время выполнения операций со структурой данных должно быть как можно меньше.
Space Complexity - Использование памяти операцией структуры данных должно быть как можно меньше.
Потребность в структуре данных
По мере того, как приложения становятся сложными и насыщенными данными, в настоящее время приложения сталкиваются с тремя распространенными проблемами.
Data Search- Рассмотрим инвентаризацию 1 миллиона (10 6 ) товаров в магазине. Если приложение должно искать элемент, оно должно искать элемент в 1 миллионе (10 6 ) элементов каждый раз, замедляя поиск. По мере роста объема данных поиск будет замедляться.
Processor speed - Скорость процессора, хотя и очень высока, снижается, если объем данных увеличивается до миллиарда записей.
Multiple requests - Поскольку тысячи пользователей могут одновременно искать данные на веб-сервере, даже быстрый сервер дает сбой при поиске данных.
Для решения вышеупомянутых проблем на помощь приходят структуры данных. Данные могут быть организованы в структуру данных таким образом, что поиск по всем элементам может не требоваться, а поиск необходимых данных может выполняться практически мгновенно.
Случаи времени исполнения
Есть три случая, которые обычно используются для относительного сравнения времени выполнения различных структур данных.
Worst Case- Это сценарий, при котором операция с определенной структурой данных занимает максимальное время. Если время наихудшего случая операции равно (n), то эта операция не займет больше времени ƒ (n), где ƒ (n) представляет функцию от n.
Average Case- Это сценарий, отображающий среднее время выполнения операции структуры данных. Если операция занимает ƒ (n) раз, то m операций займут mƒ (n) раз.
Best Case- Это сценарий, отображающий наименьшее возможное время выполнения операции структуры данных. Если операция занимает (n) времени на выполнение, тогда фактическая операция может занять время как случайное число, которое будет максимальным как (n).
Базовая терминология
Data - Данные - это значения или набор значений.
Data Item - Элемент данных относится к единице значений.
Group Items - Элементы данных, которые разделены на подпункты, называются элементами группы.
Elementary Items - Элементы данных, которые нельзя разделить, называются элементарными элементами.
Attribute and Entity - Сущность - это то, что содержит определенные атрибуты или свойства, которым могут быть присвоены значения.
Entity Set - Объекты с похожими атрибутами образуют набор объектов.
Field - Поле - это единая элементарная единица информации, представляющая атрибут объекта.
Record - Запись - это набор значений полей данного объекта.
File - Файл - это набор записей сущностей в данном наборе сущностей.