Презентация Вычислительная сложность. Базовые структуры данных и их использование в С онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Вычислительная сложность. Базовые структуры данных и их использование в С абсолютно бесплатно. Урок-презентация на эту тему содержит всего 37 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:37 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:333.50 kB
- Просмотров:48
- Скачиваний:2
- Автор:неизвестен
Слайды и текст к этой презентации:
№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 << arr[0]; // получили элемент
----------------------------------------------------------------
int *arr = new int[100];
arr[0] = 123;
delete[] arr;
№15 слайд
Содержание слайда: STL
STL (Standard Template Library) – набор алгоритмов, контейнеров и вспомогательных функций в языке С++.
Контейнеры – объекты для хранения данных. В виде них в C++ уже реализованы все базовые стуктуры.
Далее – общий обзор основных из этих стуктур.
№16 слайд
Содержание слайда: Вектор
Массив имеет фиксированный размер, что не всегда удобно в практических ситуациях.
Операции:
Получить элемент по индексу: О(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
№18 слайд
Содержание слайда: Вектор в С++
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;
}
№20 слайд
Содержание слайда: Множество
Структура данных, в которой каждый элемент хранится в единственном числе.
Операции:
Добавить элемент в множество
Удалить элемент из множества
Проверить наличие элемента во множестве
Получить размер множества
№21 слайд
Содержание слайда: Множество в С++
В С++ существует две реализации множества – 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
№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
№24 слайд
Содержание слайда: Множество в С++
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;
}
№26 слайд
Содержание слайда: Стек
Структура данных «LIFO» (Last-In First-Out).
Операции:
Добавить элемент на вершину стека: O(1)
Получить элемент с вершины стека: O(1)
Удалить элемент с вершины стека: O(1)
Определить, не пустой ли стек: O(1)
№27 слайд
Содержание слайда: Стек
Названия операций:
Добавить элемент: 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();
}
№29 слайд
Содержание слайда: Очередь
Структура данных «FIFO» (First-In First-Out).
Операции:
Добавить элемент в конец очереди: O(1)
Получить элемент с начала очереди: O(1)
Удалить элемент с начала очереди: O(1)
Определить, не пуста ли очередь: O(1)
№30 слайд
Содержание слайда: Очередь
Названия операций:
Добавить элемент в конец: 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();
}
№33 слайд
Содержание слайда: Словарь
Структура данных, в которой можно сохранять и получать значения по произвольным ключам
Операции:
Записать значение по ключу
Получить значение по ключу
Проверить наличие ключа в словаре
Получить размер словаря
№34 слайд
Содержание слайда: Словарь в С++ (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'];
№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!";
}
№37 слайд
Содержание слайда: Итого
Вектор (vector)
Множество (set)
Стек (stack)
Очередь (queue)
Словарь (map)
Скачать все slide презентации Вычислительная сложность. Базовые структуры данных и их использование в С одним архивом:
