Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

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

Автор:   •  Декабрь 12, 2023  •  Лабораторная работа  •  3,499 Слов (14 Страниц)  •  114 Просмотры

Страница 1 из 14

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

...

Скачать:   txt (12 Kb)   pdf (141.5 Kb)   docx (585.5 Kb)  
Продолжить читать еще 13 страниц(ы) »
Доступно только на Essays.club