Основы алгоритмизации и программирования. Лекция 14

Август 13, 2022

Главная
Информатика
Основы алгоритмизации и программирования. Лекция 14

Содержание

2. Обучение в университете
3. Оценки прошлого потока
4. Мем в начале
5. Содержание лекции Оценка эффективности алгоритмов Временная сложность Пространственная сложность Примеры
6. Оценка эффективности алгоритмов Время выполнения (execution time) – временная эффективность Объем потребляемой памяти (memory consumption) –
7. Факторы, влияющие на время выполнения Размер входных данных Качество реализации алгоритма на языке программирования Качество скомпилированного
8. Анализ времени выполнения алгоритмов
9. «Элементарные» операции Присваивание значения переменной Вызов функции Арифметические операции Сравнение двух значений Обращение по индексу Возвращение
10. Пример
11. Сложность алгоритма
12. Асимптотический анализ сложности алгоритмов
13. Асимптотический анализ сложности алгоритмов
14. Асимптотический анализ сложности алгоритмов Для алгоритмов обычно оценивают количество операций для следующих случаев: худший случай (worst
15. О-обозначения
16. Ω-обозначения
17. Θ-обозначения
18. Примеры
19. Свойства
20. Пример void ExampleFunc(const vector & items) { cout int middle_index = items.size() / 2; int index
21. Пример void ExampleFunc(const vector & numbers) { cout for (int number : numbers) { cout }
22. Классы сложности O(n)
23. Графическое представление
24. Наглядно Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!)
25. Пространственная сложность void bubble_sort(int k, int x[max]) { int i, j, temp; for(i=0; i for(j=0; j
26. Пример: двоичный поиск int BSRec(int arr[], int l, int r, int x) { if (r >=
27. Пример: двоичный поиск
28. Пример: двоичный поиск
29. Пример: быстрая сортировка
30. Сравнение алгоритмов сортировки
31. Пример вопроса на экзамене
32. Пример задачи на экзамене Дополнительное условие: привести расчет временной и пространственной сложности реализованного алгоритма
33. Экзамен Тест 20 вопросов с вариантами ответов 20 минут 1 попытка (естественно! ☺) Максимальная оценка –
35. Скачать презентацию

Слайд 2

Обучение в университете

Слайд 3

Оценки прошлого потока

Слайд 4

Мем в начале

Слайд 5

Содержание лекции
Оценка эффективности алгоритмов
Временная сложность
Пространственная сложность
Примеры

Слайд 6

Оценка эффективности алгоритмов
Время выполнения (execution time) – временная эффективность
Объем потребляемой памяти

(memory consumption) – пространственная эффективность

Слайд 7

Факторы, влияющие на время выполнения
Размер входных данных
Качество реализации алгоритма на языке

программирования
Качество скомпилированного кода
Производительность вычислительной машины

Слайд 8

Анализ времени выполнения алгоритмов

Слайд 9

«Элементарные» операции
Присваивание значения переменной
Вызов функции
Арифметические операции
Сравнение двух значений
Обращение по индексу
Возвращение значение

из функции
Циклы и подпрограммы состоят из последовательности простых операций

Слайд 10

Пример

Слайд 11

Сложность алгоритма

Слайд 12

Асимптотический анализ сложности алгоритмов

Слайд 13

Асимптотический анализ сложности алгоритмов

Слайд 14

Асимптотический анализ сложности алгоритмов
Для алгоритмов обычно оценивают количество операций для следующих

случаев:
худший случай (worst case)
средний случай (average case)
наилучший случай (best case)
Для записи асимптотической оценки вычислительной сложности алгоритмов используются асимптотические обозначения:
О-нотацию (Big O)

Слайд 15

О-обозначения

Слайд 16

Ω-обозначения

Слайд 17

Θ-обозначения

Слайд 18

Примеры

Слайд 19

Свойства

Слайд 20

$Пример void ExampleFunc(const vector & items) { cout int middle_index =$

Пример
void ExampleFunc(const vector& items) {
cout << items[0] << endl;
int

middle_index = items.size() / 2;
int index = 0;
while (index < middle_index) {
cout << items[index] << endl;
++index;
}
for (int i = 0; i < 100; ++i) {
cout << "hi" << endl;
}
}

Слайд 21

Пример
void ExampleFunc(const vector& numbers) {
cout << "these are the numbers:"

<< endl;
for (int number : numbers) {
cout << number << endl;
}
cout << "and these are their sums:" << endl;
for (int firstNumber : numbers) {
for (int secondNumber : numbers) {
cout << (firstNumber + secondNumber) << endl;
}
}
}

Слайд 22

Классы сложности O(n)

Слайд 23

Графическое представление

Слайд 24

Наглядно
Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!)

Слайд 25

$Пространственная сложность void bubble_sort(int k, int x[max]) { int i, j,$

Пространственная сложность
void bubble_sort(int k, int x[max]) {
int i, j, temp;

for(i=0; i < k-1; i++) {
for(j=0; j < k-i-1; j++) {
if(x[j] > x[j + 1]) {
temp = x[j];
x[j] = x[j+1];
x[j+1] = temp;
}
}
}
}

Константная сложность по памяти:
T(n)=3=O(1)

Слайд 26

Пример: двоичный поиск
int BSRec(int arr[], int l, int r, int x)

{
if (r >= l) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return mid;
if (arr[m] > x)
return BSRec(arr, l, m-1, x);
return BSRec(arr, m+1, r, x);
}
return -1;
}

int BSIter(int arr[], int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else r = m - 1;
}
return -1;
}

Слайд 27

Пример: двоичный поиск

Слайд 28

Пример: двоичный поиск

Слайд 29

Пример: быстрая сортировка

Слайд 30

Сравнение алгоритмов сортировки

Слайд 31

Пример вопроса на экзамене

Слайд 32

Пример задачи на экзамене
Дополнительное условие: привести расчет временной и пространственной сложности

реализованного алгоритма

Слайд 33

Экзамен
Тест
20 вопросов с вариантами ответов
20 минут
1 попытка (естественно! ☺)
Максимальная оценка –

10 баллов
Задача
Для тех, кто ответит правильно на 16+ вопросов (80%)
Тест + задача = 10 баллов

Основы алгоритмизации и программирования. Лекция 14

Содержание

Обучение в университете

Оценки прошлого потока

Мем в начале

Содержание лекцииОценка эффективности алгоритмовВременная сложностьПространственная сложностьПримеры

Оценка эффективности алгоритмовВремя выполнения (execution time) – временная эффективностьОбъем потребляемой памяти

Факторы, влияющие на время выполненияРазмер входных данныхКачество реализации алгоритма на языке

Анализ времени выполнения алгоритмов

«Элементарные» операцииПрисваивание значения переменнойВызов функцииАрифметические операцииСравнение двух значенийОбращение по индексуВозвращение значение

Пример

Сложность алгоритма

Асимптотический анализ сложности алгоритмов

Асимптотический анализ сложности алгоритмов

Асимптотический анализ сложности алгоритмовДля алгоритмов обычно оценивают количество операций для следующих

О-обозначения

Ω-обозначения

Θ-обозначения

Примеры

Свойства

Примерvoid ExampleFunc(const vector& items) { cout << items[0] << endl; int

Примерvoid ExampleFunc(const vector& numbers) { cout << "these are the numbers:"

Классы сложности O(n)

Графическое представление

НаглядноBig-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!)

Пространственная сложностьvoid bubble_sort(int k, int x[max]) { int i, j, temp;

Пример: двоичный поискint BSRec(int arr[], int l, int r, int x)

Пример: двоичный поиск

Пример: двоичный поиск

Пример: быстрая сортировка

Сравнение алгоритмов сортировки

Пример вопроса на экзамене

Пример задачи на экзаменеДополнительное условие: привести расчет временной и пространственной сложности

ЭкзаменТест20 вопросов с вариантами ответов20 минут1 попытка (естественно! ☺)Максимальная оценка –

Похожие презентации

Содержание лекции
Оценка эффективности алгоритмов
Временная сложность
Пространственная сложность
Примеры

Оценка эффективности алгоритмов
Время выполнения (execution time) – временная эффективность
Объем потребляемой памяти

Факторы, влияющие на время выполнения
Размер входных данных
Качество реализации алгоритма на языке

Асимптотический анализ сложности алгоритмов
Для алгоритмов обычно оценивают количество операций для следующих

Пример
void ExampleFunc(const vector& items) {
cout << items[0] << endl;
int

Пример
void ExampleFunc(const vector& numbers) {
cout << "these are the numbers:"

Наглядно
Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!)

Пространственная сложность
void bubble_sort(int k, int x[max]) {
int i, j, temp;

Пример: двоичный поиск
int BSRec(int arr[], int l, int r, int x)

Пример задачи на экзамене
Дополнительное условие: привести расчет временной и пространственной сложности

Экзамен
Тест
20 вопросов с вариантами ответов
20 минут
1 попытка (естественно! ☺)
Максимальная оценка –