Вычислительная сложность. Базовые структуры данных и их использование в С++

Нажмите для полного просмотра!

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №2

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №3

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №4

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №5

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №6

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №7

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №8

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №9

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №10

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №11

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №12

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №13

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №14

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №15

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №16

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №17

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №18

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №19

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №20

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №21

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №22

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №23

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №24

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №25

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №26

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №27

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №28

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №29

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №30

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №31

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №32

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №33

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №34

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №35

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №36

Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №37

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Вычислительная сложность. Базовые структуры данных и их использование в С++. Доклад-сообщение содержит 37 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Занятие 16.12.17

Слайд 2

Описание слайда:

Основные пункты Вычислительная сложность Базовые структуры данных и их использование в С++

Слайд 3

Описание слайда:

Вычислительная сложность Нужно как-то сравнивать ресурсы, которые будут потрачены тем или иным алгоритмом Они включают: Время процессора Занимаемая память

Слайд 4

Описание слайда:

Вычислительная сложность Вариант #1 – точный подсчет, например, отдельных команд процессора Проблемы: Команды занимают разное время У разных процессоров разные наборы команд Громоздкость выражений и сложность подсчета

Слайд 5

Описание слайда:

Вычислительная сложность Как правило, достаточно сравнивать поведение алгоритмов в целом Вариант #2 – сравнивать общий вид зависимости использованного времени/памяти от входных данных

Слайд 6

Описание слайда:

«О» большое

Слайд 7

Описание слайда:

«О» большое Объяснение на примерах: мы говорим, что алгоритм имеет сложность O(n) операций, если с ростом размера входных данных затрачиваемое время/ресурсы растут линейно

Слайд 8

Описание слайда:

«О» большое O(n): n = 10, операций 10 n = 20, операций 20 Но так же под О(n) подходит: n = 1, операций 103 n = 2, операций 206 n = 1000, операций 112 910 главное – что в целом растет линейно

Слайд 9

Описание слайда:

«О» большое Мы говорим, что алгоритм имеет сложность O(n^2) операций, если с ростом размера входных данных затрачиваемое время/ресурсы растут квадратично. n = 10, операций около 100 n = 20, операций около 400

Слайд 10

Описание слайда:

«О» большое Часто можно увидеть: O(1) O(log n) O(sqrt n) O(n) O(n * log n) O(n ^ 2) O(2 ^ n)

Слайд 11

Описание слайда:

«О» большое Что такое n? Примеры: Определение простоты числа n: n – само число Сортировка массива: n – размер массива Работа со строкой: n – размер строки

Слайд 12

Описание слайда:

Базовые структуры данных Массив Вектор Множество Стек Очередь Словарь

Слайд 13

Описание слайда:

Массив Последовательность элементов фиксированного размера. Операции: Получить элемент по индексу: О(1) времени Записать элемент по индексу: O(1) времени

Слайд 14

Описание слайда:

Массив в С++ int arr[100]; arr[0] = 123; // записали элемент cout

Слайд 15

Описание слайда:

STL STL (Standard Template Library) – набор алгоритмов, контейнеров и вспомогательных функций в языке С++. Контейнеры – объекты для хранения данных. В виде них в C++ уже реализованы все базовые стуктуры. Далее – общий обзор основных из этих стуктур.

Слайд 16

Описание слайда:

Вектор Массив имеет фиксированный размер, что не всегда удобно в практических ситуациях. Операции: Получить элемент по индексу: О(1) времени Записать элемент по индексу: O(1) Получить текущий размер вектора: O(1) Добавить элемент в конец вектора: О(1)*

Слайд 17

Описание слайда:

Вектор в С++ #include vector tmp; tmp.push_back(1); tmp.push_back(2); tmp.push_back(3); cout

Слайд 18

$Вектор в С++ vector numbers; cin >> n; for (int i = 0; i < n; i++) { int tmp; cin >> tmp; numbers.push_back(tmp); }$

Описание слайда:

Вектор в С++ vector numbers; cin >> n; for (int i = 0; i < n; i++) { int tmp; cin >> tmp; numbers.push_back(tmp); }

Слайд 19

Описание слайда:

Вектор в С++ vector numbers; // … for (int i = 0; i < number.size(); i++) { cout

Слайд 20

Описание слайда:

Множество Структура данных, в которой каждый элемент хранится в единственном числе. Операции: Добавить элемент в множество Удалить элемент из множества Проверить наличие элемента во множестве Получить размер множества

Слайд 21

Описание слайда:

Множество в С++ В С++ существует две реализации множества – set и unordered_set. Пока остановимся только на первой. Занимаемая память – O(n log n) Добавление элемента – O(log n) Удаление элемента – О(log n) Проверка элемента – O(log n)

Слайд 22

Описание слайда:

Множество в С++ #include set my_set; my_set.insert(3); my_set.insert(4); my_set.insert(3); cout

Слайд 23

Описание слайда:

Множество в С++ set my_set; my_set.insert(1); my_set.insert(2); my_set.erase(1); my_set.erase(2); cout

Слайд 24

$Множество в С++ set my_set; // Определим, есть ли там элемент 2 if (my_set.find(2) != my_set.end()) { cout$

Описание слайда:

Множество в С++ set my_set; // Определим, есть ли там элемент 2 if (my_set.find(2) != my_set.end()) { cout

Слайд 25

$Множество в С++ set my_set; // Вывести все элементы множества for (auto it = my_set.begin(); it != my_set.end(); it++) { cout$

Описание слайда:

Множество в С++ set my_set; // Вывести все элементы множества for (auto it = my_set.begin(); it != my_set.end(); it++) { cout

Слайд 26

Описание слайда:

Стек Структура данных «LIFO» (Last-In First-Out). Операции: Добавить элемент на вершину стека: O(1) Получить элемент с вершины стека: O(1) Удалить элемент с вершины стека: O(1) Определить, не пустой ли стек: O(1)

Слайд 27

Описание слайда:

Стек Названия операций: Добавить элемент: push Получить элемент на вершине: top Удалить элемент с вершины: pop Проверить на пустоту: empty

Слайд 28

Описание слайда:

Стек в С++ stack s; s.push(1); s.push(2); s.push(3); while (!s.empty()) { cout

Слайд 29

Описание слайда:

Очередь Структура данных «FIFO» (First-In First-Out). Операции: Добавить элемент в конец очереди: O(1) Получить элемент с начала очереди: O(1) Удалить элемент с начала очереди: O(1) Определить, не пуста ли очередь: O(1)

Слайд 30

Описание слайда:

Очередь Названия операций: Добавить элемент в конец: push Получить элемент в начале: front Удалить элемент в начале: pop Проверить на пустоту: empty

Слайд 31

Описание слайда:

Стек | Очередь

Слайд 32

Описание слайда:

Очередь в С++ queue q; q.push(1); q.push(2); q.push(3); while (!q.empty()) { cout

Слайд 33

Описание слайда:

Словарь Структура данных, в которой можно сохранять и получать значения по произвольным ключам Операции: Записать значение по ключу Получить значение по ключу Проверить наличие ключа в словаре Получить размер словаря

Слайд 34

Описание слайда:

Словарь в С++ (map) Занимаемая память: O(n log n) Сложность операций: Получить значение по ключу: O(log n) Записать значение по ключу: O(log n) Проверить наличие ключа: O(log n) Получить размер словаря: O(1)