Способы хранения множеств в памяти ЭВМ
Автор: grolx24 • Декабрь 12, 2023 • Лабораторная работа • 3,499 Слов (14 Страниц) • 114 Просмотры
1.Цель работы
Исследование четырех способов хранения множеств в памяти ЭВМ.
2.Задание
Составить и отладить программу, реализующую вычисление множества.
Множество: содержит все буквы из A и B, но не содержит букв, являющихся общими для C и D.
Универсум: строчные русские буквы
3.Формализация задания
Формула для вычисления пятого множества: E = (A⋃B) \ (C⋂D)
4.Контрольные тесты
- A = аб, B =вг, C = бв, D = б. ⇒ E = авг
[pic 1]
- A = абдклмнопртфчъэю,
B = авдежийлмопртхцчшщъэ,
C = зйнорсшыэю,
D = вгдежкмопуфхцъьэю. ⇒
E = абдклмнпртфчъвежийчцшщ
[pic 2]
- A = абвгдежзийклмнопрстуфхцчшщъыьэюя,
B = абвгдежзийклмнопрстуфхцчшщъыьэюя,
C = абвгдежзийклмнопрстуфхцчшщъыьэюя,
D = абвгдежзийклмнопрстуфхцчшщъыьэюя. ⇒
E = абвгдежзийклмнопрстуфхцчшщъыьэюя
[pic 3]
- A =,
B =,
C =,
D =. ⇒
E =
[pic 4]
- A = абвгдежзийклмноп,
B = абвгдежзийклмноп,
C = абвгдежзийклмноп,
D = абвгдежзийклмноп. ⇒
E = абвгдежзийклмноп
[pic 5]
Пояснение: в первых четырех строках исходные множества, в последних четырех строках искомое множество E вычисленное с использованием разных структур данных. Использованная структура данных указана в скобках. Также указано время на вычисление множества E с использованием конкретной структуры данных.
5.Временнная сложность
- Структура данных – массив символов:
Ожидаемая временная сложность: O(n^2)
Фактическая временная сложность: O(n^(1/3))
- Структура данных – машинное слово:
Ожидаемая временная сложность O(1)
Фактическая временная сложность O(1)
- Структура данных – линейный список:
Ожидаемая временная сложность: O(n^2)
Фактическая временная сложность: O(n^(1/2))
- Структура данных – массив битов:
Ожидаемая временная сложность: O(1)
Фактическая временная сложность: O(1)
6.Результаты времени обработки
- (массив символов)
Наблюдалась зависимость времени обработки от размера данных (при увеличении объёма данных в 8 раз, время увеличилось в 2 раза).
- (машинное слово)
Зависимости времени обработки данных от объёма данных не наблюдалось
- (линейный список)
Наблюдалась зависимость времени обработки от размера данных (при увеличении объёма данных в 8 раз, время увеличилось в 3 раза).
- (массив битов)
Зависимости времени обработки данных от объёма данных не наблюдалось
7.Выводы о результатах испытаний
- Способы, зависимые от объёма данных:
Массив символов и линейный список. Несмотря на то, что линейный список показал лучшие результаты во всех тестах, фактическая временная сложность лучше у массива символов, что говорит о том, что возможно при увеличении объёма данных этот способ был бы предпочтительней.
- Способы, независимые от объёма данных:
Массив битов и машинное слово: Основываясь на результатах тестов обработка массива битов предпочтительней.
8.Список использованных источников
1) Колинько П.Г. Пользовательские структуры данных: Методические указания по дисциплине «Алгоритмы и структуры данных, часть 1»
9.Текст программы
Язык с++ 14.
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
struct list
{
char a = 0;
list* next = NULL;
list(char s, list* n = nullptr) : a(s), next(n) {}
~list() { delete next; }
...