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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №1Вычислительная сложность. Базовые структуры данных и их использование в С++, слайд №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
Описание слайда:
Занятие 16.12.17

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


«О» большое
Описание слайда:
«О» большое

Слайд 7


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

Слайд 8


«О» большое O(n): n = 10, операций 10 n = 20, операций 20 Но так же под О(n) подходит: n = 1, операций 103 n = 2, операций 206 n = 1000, операций 112 910 главное – что в целом растет линейно
Описание слайда:
«О» большое 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
Описание слайда:
«О» большое Мы говорим, что алгоритм имеет сложность 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)
Описание слайда:
«О» большое Часто можно увидеть: 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 – размер строки
Описание слайда:
«О» большое Что такое n? Примеры: Определение простоты числа n: n – само число Сортировка массива: n – размер массива Работа со строкой: n – размер строки

Слайд 12


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

Слайд 13


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

Слайд 14


Массив в С++ int arr[100]; arr[0] = 123; // записали элемент cout << arr[0]; // получили элемент ---------------------------------------------------------------- int *arr = new int[100]; arr[0] = 123; delete[] arr;
Описание слайда:
Массив в С++ int arr[100]; arr[0] = 123; // записали элемент cout << arr[0]; // получили элемент ---------------------------------------------------------------- int *arr = new int[100]; arr[0] = 123; delete[] arr;

Слайд 15


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

Слайд 16


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

Слайд 17


Вектор в С++ #include <vector> vector<int> tmp; tmp.push_back(1); tmp.push_back(2); tmp.push_back(3); cout << tmp [0] << tmp[1] << tmp[2]; // 1 2 3
Описание слайда:
Вектор в С++ #include <vector> vector<int> tmp; tmp.push_back(1); tmp.push_back(2); tmp.push_back(3); cout << tmp [0] << tmp[1] << tmp[2]; // 1 2 3

Слайд 18


Вектор в С++ vector<int> numbers; cin >> n; for (int i = 0; i < n; i++) { int tmp; cin >> tmp; numbers.push_back(tmp); }
Описание слайда:
Вектор в С++ vector<int> numbers; cin >> n; for (int i = 0; i < n; i++) { int tmp; cin >> tmp; numbers.push_back(tmp); }

Слайд 19


Вектор в С++ vector<int> numbers; // … for (int i = 0; i < number.size(); i++) { cout << numbers[i] << endl; }
Описание слайда:
Вектор в С++ vector<int> numbers; // … for (int i = 0; i < number.size(); i++) { cout << numbers[i] << endl; }

Слайд 20


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

Слайд 21


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

Слайд 22


Множество в С++ #include <set> set<int> my_set; my_set.insert(3); my_set.insert(4); my_set.insert(3); cout << my_set.size(); // 2
Описание слайда:
Множество в С++ #include <set> set<int> my_set; my_set.insert(3); my_set.insert(4); my_set.insert(3); cout << my_set.size(); // 2

Слайд 23


Множество в С++ set<int> my_set; my_set.insert(1); my_set.insert(2); my_set.erase(1); my_set.erase(2); cout << my_set.size(); // 0
Описание слайда:
Множество в С++ set<int> my_set; my_set.insert(1); my_set.insert(2); my_set.erase(1); my_set.erase(2); cout << my_set.size(); // 0

Слайд 24


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

Слайд 25


Множество в С++ set<int> my_set; // Вывести все элементы множества for (auto it = my_set.begin(); it != my_set.end(); it++) { cout << *it << endl; }
Описание слайда:
Множество в С++ set<int> my_set; // Вывести все элементы множества for (auto it = my_set.begin(); it != my_set.end(); it++) { cout << *it << endl; }

Слайд 26


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

Слайд 27


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

Слайд 28


Стек в С++ stack<int> s; s.push(1); s.push(2); s.push(3); while (!s.empty()) { cout << s.top() << " "; // 3 2 1 s.pop(); }
Описание слайда:
Стек в С++ stack<int> s; s.push(1); s.push(2); s.push(3); while (!s.empty()) { cout << s.top() << " "; // 3 2 1 s.pop(); }

Слайд 29


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

Слайд 30


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

Слайд 31


Стек | Очередь
Описание слайда:
Стек | Очередь

Слайд 32


Очередь в С++ queue<int> q; q.push(1); q.push(2); q.push(3); while (!q.empty()) { cout << q.front() << " "; // 1 2 3 q.pop(); }
Описание слайда:
Очередь в С++ queue<int> q; q.push(1); q.push(2); q.push(3); while (!q.empty()) { cout << q.front() << " "; // 1 2 3 q.pop(); }

Слайд 33


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

Слайд 34


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

Слайд 35


Словарь в С++ (map) #include <map> map<char, int> my_map; my_map['A'] = 5; my_map['B'] = 6; cout << "A is " << my_map['A'];
Описание слайда:
Словарь в С++ (map) #include <map> map<char, int> my_map; my_map['A'] = 5; my_map['B'] = 6; cout << "A is " << my_map['A'];

Слайд 36


Словарь в С++ (map) #include <map> map<char, int> my_map; my_map['A'] = 5; if (my_map.find('A') != my_map.end()) { cout << "Key 'A' exists!"; }
Описание слайда:
Словарь в С++ (map) #include <map> map<char, int> my_map; my_map['A'] = 5; if (my_map.find('A') != my_map.end()) { cout << "Key 'A' exists!"; }

Слайд 37


Итого Вектор (vector) Множество (set) Стек (stack) Очередь (queue) Словарь (map)
Описание слайда:
Итого Вектор (vector) Множество (set) Стек (stack) Очередь (queue) Словарь (map)

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию