Функция. Оценка сложности алгоритмов. Алгоритмы сортировки

1.

2 семестр

2.

Вводим новую систему оценивания
• 3 оценки: 5, точка и 2
• Набрал 3 точки => получилась одна двойка
• Невыполнение дз или не успевание сделать n-ое количество
задач на паре превращаются в точку
• За опоздания точка

3.

Для начала
Что такое функция?

4.

Функция:
• фрагмент программного кода, к которому можно обратиться из
другого места программы
• Функцией называется соответствие между двумя множествами,
при котором каждому элементу одного множества соответствует
единственный элемент другого множества.

5.

Оценка сложности
алгоритма
time complexity
space complexity

6.

Критерии оценки алгоритма
• Вычислительная временная сложность (time complexity) — это
максимальное возможное количество выполненных алгоритмом
элементарных операций, как функция от размера входных
данных.
• Вычислительная ёмкостная сложность (space complexity) — это
максимальный возможный размер занятой алгоритмом
дополнительной памяти, как функция от размера входных
данных.

7.

Пример
for (int i=0; i < n; i++)
count++;
Посчитаем количество элементарных операций:
Для i = 0
Для i < n
Для i++
Для count++

8.

Пример
for (int i=0; i < n; i++)
count++;
Посчитаем количество элементарных операций:
Для i = 0
=> 1
Для i < n
=> n + 1
Для i++ => (i=i+1) => 2n
Для count++ => (count=count+1) => 2n

9.

Итого:
for (int i=0; i < n; i++)
count++;
Получаем временную сложность алгоритма:

10.

Пример:

11.

Итого
• Посчитаем функцию сложности:
• i = 0 выполнится лишь однажды
• i<n внутри while выполнится n+1 раз
• i+=1 выполнится n раз (+= это две элементарные операции)
• цикл for начнет выполняться n раз и каждый раз:
• j=0 выполнится один раз
• j<n выполнится n+1 раз
• j++ выполнится n раз (++ это две элементарные операции)
• count++ выполнится n раз (++ это две элементарные операции)

12.

Итого, сложность

13.

Асимптотическая оценка и
нотация большого О
Асимптотическая оценка даёт нам
примерное представление, при
каком размере задачи (того самого
n, от которого зависит функция
сложности), можно ожидать
приемлемой скорости выполнения.

14.

Примеры
О – степень
сложности не более
числа n
Ѳ – степень
сложности в
точности число n

15.

Пример
Какая операция
выполняется
больше всего раз?

16.

17.

Красная зона –> ожидание результата не
менее суток

18.

https://ulearn.me/

19.

Рекурсия
Рекурсия — это функция, которая
вызывает саму себя.
Понятие функция используется в
рамках информатики.

20.

Пример

21.

Пример
В чем
проблема?

22.

23.

Итог:
1)Условие для не рекурсивного возврата ( условие остановки)
2)Рекурсивный возврат

24.

Пример

25.

Пример с несколькими условиями

26.

Чем больше тем лучше, минимум 5

27.

ДЗ => задача соответствует номеру в
списке

28.

Поиск в массиве
Линейный и бинарный поиск

29.

int required_number = 4;
int * mas = new int[n];
for (int i = 0; i < n; i++)
{
if (mas[n] == required_number)
{
std::cout << i;
break;
}
Что делает этот код и
какая у него временная
сложность?

30.

Бинарный поиск
• Поиск осуществляется только в отсортированном массиве
• Работает на порядок быстрее, чем линейный поиск

31.

32.

33.

34.

35.

Источники
• https://brestprog.by/topics/binsearch/
• https://codelessons.dev/ru/binarnyj-poisk-po-massivu-c/

36.

Алгоритмы сортировки
• Простые сортировки
• Эффективные
сортировки

37.

38.

Простые сортировки

39.

Сортировка пузырьком
Здесь нужно последовательно сравнивать значения соседних
элементов и менять числа местами, если предыдущее
оказывается больше последующего. Таким образом
элементы с большими значениями оказываются в конце
списка, а с меньшими остаются в начале.

40.

Код. Разбор
void BubbleSort(int* array, int array_size) {
for (int idx_i = 0; idx_i + 1 < array_size; idx_i++) {
for (int idx_j = 0; idx_j + 1 < array_size - idx_i; idx_j++) {
if (array[idx_j + 1] < array[idx_j]) {
swap(array[idx_j], array[idx_j + 1]);
}
}
}
}

41.

Сортировка вставками
При сортировке вставками массив
постепенно перебирается слева направо.
При этом каждый последующий элемент
размещается так, чтобы он оказался между
ближайшими элементами с минимальным и
максимальным значением.

42.

Код. Разбор
void InsertionSort(int* array, int num_of_elm) {
for (int i = 1; i < num_of_elm; i++) {
int current_num = array[i];
int j = i;
while (j > 0 && array[j - 1] > current_num) {
array[j] = array[j - 1];
--j;
}
array[j] = current_num;
}
}

43.

Сортировка выбором
Сначала нужно рассмотреть подмножество массива и
найти в нём максимум (или минимум). Затем
выбранное значение меняют местами со значением
первого неотсортированного элемента. Этот шаг нужно
повторять до тех пор, пока в массиве не закончатся
неотсортированные подмассивы.

44.

Код. Разбор
• void SelectionSort(vector<int>& values) {
• for (auto i = values.begin(); i != values.end(); ++i) {
• auto j = std::min_element(i, values.end());
• swap(*i, *j);
• }
•}

45.

Задачи

46.

Эффективные сортировки

47.

Быстрая сортировка
Этот алгоритм состоит из трёх шагов.
1. Сначала из массива нужно выбрать один
элемент — его обычно называют опорным.
2. Затем другие элементы в массиве
перераспределяют так, чтобы элементы меньше
опорного оказались до него, а большие или
равные — после.
3. А дальше рекурсивно применяют первые два
шага к подмассивам справа и слева от опорного
значения.

48.

Сортировки слиянием
Сортировка слиянием пригодится для таких
структур данных, в которых доступ к элементам
осуществляется последовательно (например, для
потоков). Здесь массив разбивается на две
примерно равные части и каждая из них
сортируется по отдельности. Затем два
отсортированных подмассива сливаются в один.

49.

Пирамидальная сортировка
При этой сортировке сначала строится пирамида из
элементов исходного массива. Пирамида (или
двоичная куча) — это способ представления
элементов, при котором от каждого узла может
отходить не больше двух ответвлений. А значение в
родительском узле должно быть больше значений в
его двух дочерних узлах.

50.

Задачи

51.

Источники
https://habr.com/ru/articles/188010/
https://education.yandex.ru/journal/osnovnye-vidy-sortirovok-i-primery-ikh-realizatsii

52.

Type struct and vector

53.

Vector
• Вектор представляет контейнер, который содержит
коллекцию объектов одного типа.
• #include <vector>
• Вектор является динамическим одномерным массивом.

54.

Базовые операции с объектами класса
vector

55.

Решаем задачку на массивы через вектор

56.

5 Задачек из Полякова используя vector

57.

Источники
• https://metanit.com/cpp/tutorial/7.2.php
• https://learn.microsoft.com/ru-ru/cpp/standard-library/vectorclass?view=msvc-170

58.

Struct
• Собственный тип данных
• Чтобы определить структуру необходимо:
struct имя_структуры
{
компоненты_структуры
};

59.

Возникает понятие экземпляр

60.

Примеры.
• 1. Объект: Смартфон.
Характеристики объекта: Фирма-производитель, объем
встроенной памяти, цена.
• 2. Объект: Ноутбук.
Характеристики объекта: Фирма-производитель, модель
процессора, наличие игровой видеокарты.
• 3. Объект: Электронная книга.
Характеристики объекта: Фирма-производитель, размер экрана,
наличие подсветки экрана.
• 4. Объект: Монитор.
Характеристики объекта: Фирма-производитель, размер экрана,
цена.

61.

Задание
1. Создать по 2 экземпляра структуры
2. Создать функцию ввода параметром принимать указатель на
структуру.
3. Создать функцию вывода, которая печатает сведения о
экземпляре структуры.
4. Функция, которая создает динамически экземпляры структуры,
сохраняет их в вектор.

62.

Потоки ввода вывода
• istream и wistream: читают данные с
потока
• ostream и wostream: записывают
данные в поток
• iostream и wiostream: читают и
записывают данные в поток

63.

Поток вывода
Стандартные объекты: std::cout <<; std::cerr << ;
Два операнда << левый показывает, куда осуществляется
вывод, правый что выводится.

64.

Поток ввода
Стандартный объект: std::cin >> ;
Также два операнда >> левый показывает откуда осуществляется
ввод, правый куда записывать

65.

Работа с файлами

66.

Открытие и закрытие файлов
• std::ofstream out;
// поток для записи
• out.open("hello1.txt"); // окрываем файл для записи
• std::ifstream in;
// поток для чтения
• in.open("hello4.txt"); // окрываем файл для чтения
• std::fstream fs;
// поток для чтения-записи
• fs.open("hello5.txt"); // окрываем файл для чтения-записи

67.

Чтение и запись файлов

68.

Чтение и запись файлов

69.

Задание
• Создать файл, сделать запись в файл, и считать из файла

70.

КР. Указатели и массивы
1. Что такое указатель?
2. Что такое массив?
3. Как массивы хранятся в памяти компьютера?
4. Напишите определение структуры “Человек”, с характеристиками: пол,
возраст, страна рождения. Определите 1 экземпляр этой структуры.
5. Укажите временную сложность алгоритмов
6. Создайте динамический массив целого типа состоящий из 5 элементов
на языке C/C++.

71.

72.

с

73.

Списки
• Что такое списки?
• Отличие от массивов

74.

Список

75.

Проблема массивов
• Добавление нового элемента. При добавлении элемента в
массив, создается массив большего размера, затем элементы
старого массива перезаписываются в новый, затем добавляется
новый элемент. Временная сложность записи O(n). Сложность по
памяти n + n + k, где n – размер старого массива, k – кол-во
добавленных элементов.

76.

Отличие списка от массива
Массив
1. Элементы массива хранятся в
памяти друг за другом.
2. Для создания массива, мы
должны заранее знать
количество элементов.
3. Для добавления нового элемента
нужно выделить новый массив.
4. Чтобы обратиться к любому
элементу, достаточно указать его
индекс.
Список
1. Элементы списка хранятся в
памяти независимо друг от
друга
2. Для создания списка
достаточно создать указатель.
3. Для добавления элемента,
нужно выделить память только
под сам элемент.
4. Чтобы обратиться к элементу
нужно найти адрес этого
элемента через цикл.

77.

Списки

78.

А теперь… Презентации из НГТУ

79.

Решаем задачу без смс и регистрации

80.

Источники
• https://metanit.com/cpp/tutorial/7.6.php
• https://metanit.com/cpp/tutorial/7.7.php
• Презентации из НГТУ

81.

Задание на 2 пары
• Реализовать очередь и стек на массивах и на
списках
• Должны быть реализованы операции:
• Добавления элемента О(1)
• Извлечение элемента О(1)
• Использовать структуры шаблонного типа при
реализции

82.

83.

Отчет
• Текст программы
• Результат сравнения скоростей добавления, извлечения…

84.

Второе задание
• Создать отображение: буквы на отрицательное
целое число, используя массив
• Реализовать операции:
• добавления соответствия О(1)
• удаление соответствия О(1)

85.

Очереди и стеки

86.

Деревья

87.

Heap (Куча)

88.

Графы

89.

1. Сложность алгосов (временная и пространственная)
2. Рекурсия
3. Алгоритмы поиска в массиве: линейный и бинарный отличия –>
переход к сортировкам
4. Сортировки: пузырек и квадратичные сортировки (выбор типа
сортировки)
5. Быстрая сортировка и сортировка слиянием
6. Пирамидальная сортировка и сортировка вставками

90.

7. Списки (односвязный, двусвязный) теория + пример
8. Односвязный список практика
9. Стек, очередь, дек, теория + пример
10. Стек, очередь, дек практика
11. Деревья теория + пример (2-3)
12. Деревья практика (2-3)
13. Графы теория
14. Графы обход в глубину
15. Графы обход в ширину
16. Графы алгоритм дейкстры