Семинар3

1.

Кафедра компьютерной безопасности
ЯЗЫКИ
ПРОГРАММИРОВАНИЯ
СКБ22*
Москва, 2022

2.

ЗАЧЕМ НУЖНЫ АЛГОРИТМЫ?
1. Эффективное решение задач (скорость, память)
2. Дополнительная готовность к собеседованию
3. Тренируем мозг
4. Формирует у программистов одни базовые
понятия
Москва, 2022

3.

ЛИНЕЙНЫЙ ПОИСК
Дан массив целых чисел длины N. Нужно найти в
данном массиве заданное число x и вернуть его
индекс. Если элемента в массиве нет — вернуть -1
Москва, 2022

4.

Москва, 2022
Сколько элементов массива будет
рассмотрено в этом алгоритме?

5.

Москва, 2022
Сколько элементов будет рассмотрено
в худшем случае?

6.

Москва, 2022
Вычислительная сложность алгоритма
линейно зависит от размера входных
данных.

7.

Москва, 2022
Дан массив целых чисел длины N. Нужно найти в
данном массиве заданное число x и вернуть его
индекс. Если элемента в массиве нет — вернуть -1

8.

Москва, 2022
Вычислительная сложность алгоритма
Размер входных данных
Линейная зависимость

9.

БИНАРНЫЙ ПОИСК
Дан массив целых чисел длины N. Нужно найти в
данном массиве заданное число x и вернуть его
индекс. Если элемента в массиве нет — вернуть -1
Москва, 2022

10.

СЛОЖНОСТЬ АЛГОРИТМА, О БОЛЬШОЕ, О-НОТАЦИЯ
Москва, 2022

11.

АСИМПТОТИЧЕСКАЯ
СЛОЖНОСТЬ
O(1) — константная зависимость
O(n) — линейная зависимость
O(log n) — логарифмическая зависимость
O(n^2) — квадратичная зависимость
O(n^3) — кубическая зависимость
O(2^n) — экспоненциальная зависимость
Москва, 2022

12.

ОЦЕНКА СЛОЖНОСТИ
Москва, 2022

13.

ОЦЕНКА СЛОЖНОСТИ
Москва, 2022

14.

ОЦЕНКА СЛОЖНОСТИ
Москва, 2022

15.

ОЦЕНКА СЛОЖНОСТИ
Москва, 2022

16.

АЛГОРИТМ КАК ПИСАТЬ АЛГОРИТМ
1. Слушайте (читайте)
2. Представьте пример
3. Придумайте наивное решение
4. Оптимизируйте
5. Проведите пошаговый разбор
6. Напишите код
7. Тестируйте
Москва, 2022

17.

КАК ПРИДУМЫВАТЬ ПРИМЕРЫ
1. Общий случай
2. Граничные значения (мин, макс)
Москва, 2022

18.

ИЗМЕРИТЬ ВРЕМЯ ВЫПОЛНЕНИЯ ПРОГРАММЫ
Москва, 2022