Способы хранения множеств в памяти ЭВМ

1.Цель работы

Исследование четырех способов хранения множеств в памяти ЭВМ.

2.Задание

Составить и отладить программу, реализующую вычисление множества.

Множество: содержит все буквы из A и B, но не содержит букв, являющихся общими для C и D.

Универсум: строчные русские буквы

3.Формализация задания

Формула для вычисления пятого множества: E = (A⋃B) \ (C⋂D) 

4.Контрольные тесты

1. A = аб, B =вг, C = бв, D = б. ⇒ E = авг

[pic 1]

1. A = абдклмнопртфчъэю,

B = авдежийлмопртхцчшщъэ,

C = зйнорсшыэю,

D = вгдежкмопуфхцъьэю. ⇒

E = абдклмнпртфчъвежийчцшщ

[pic 2]

1. A = абвгдежзийклмнопрстуфхцчшщъыьэюя,

B = абвгдежзийклмнопрстуфхцчшщъыьэюя,

C = абвгдежзийклмнопрстуфхцчшщъыьэюя,

D = абвгдежзийклмнопрстуфхцчшщъыьэюя. ⇒

E = абвгдежзийклмнопрстуфхцчшщъыьэюя

[pic 3]

1. A =,

B =,

C =,

D =. ⇒

E =

[pic 4]

1. A = абвгдежзийклмноп,

B = абвгдежзийклмноп,

C = абвгдежзийклмноп,

D = абвгдежзийклмноп. ⇒

E = абвгдежзийклмноп

[pic 5]

Пояснение: в первых четырех строках исходные множества, в последних четырех строках искомое множество E вычисленное с использованием разных структур данных. Использованная структура данных указана в скобках. Также указано время на вычисление множества E с использованием конкретной структуры данных.

5.Временнная сложность

1. Структура данных – массив символов:

Ожидаемая временная сложность: O(n^2)

Фактическая временная сложность: O(n^(1/3))

1. Структура данных – машинное слово:

Ожидаемая временная сложность O(1)

Фактическая временная сложность O(1)

1. Структура данных – линейный список:

Ожидаемая временная сложность: O(n^2)

Фактическая временная сложность: O(n^(1/2))

1. Структура данных – массив битов:

Ожидаемая временная сложность: O(1)

Фактическая временная сложность: O(1)

6.Результаты времени обработки

1. (массив символов)

Наблюдалась зависимость времени обработки от размера данных (при увеличении объёма данных в 8 раз, время увеличилось в 2 раза).

1. (машинное слово)

Зависимости времени обработки данных от объёма данных не наблюдалось

1. (линейный список)

Наблюдалась зависимость времени обработки от размера данных (при увеличении объёма данных в 8 раз, время увеличилось в 3 раза).

1. (массив битов)

Зависимости времени обработки данных от объёма данных не наблюдалось

7.Выводы о результатах испытаний

1. Способы, зависимые от объёма данных:

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

1. Способы, независимые от объёма данных:

Массив битов и машинное слово: Основываясь на результатах тестов обработка массива битов предпочтительней.

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; }