Практика с реальными алгоритмами

Основы информатики

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Популярные алгоритмы: сортировка и поиск

Сортировка

Используется, когда нужно упорядочить данные

Примеры из жизни:

Интернет-магазин: сортировка по цене, рейтингу, популярности.
Календарь: сортировка событий по дате и времени.

Поиск

Используется, когда нужно найти нужный элемент

Примеры из жизни:

Интернет-магазин: поиск книги по названию.
Служба поддержки: поиск предыдущих обращений по имени клиента.

Алгоритмы сортировки: пузырьковая и быстрая

Пузырьковая сортировка Анимация, демонстрирующая работу пузырьковой сортировки

Пузырьковая сортировка: сравнение, обмен, повтор, проход.
Временная сложность: $O(n^2)$.
При миллионах товаров в интернет-магазине сложность растёт экспоненциально по мере расширения каталога.

Быстрая сортировка Анимация, демонстрирующая работу быстрой сортировки

Быстрая сортировка: разделение, опорный элемент, сортировка, слияние.
Временная сложность: O(n log n).
При миллионах товаров в интернет-магазине масштабируется значительно лучше.

Алгоритмы поиска: линейный и бинарный

Линейный поиск Анимация, демонстрирующая работу линейного поиска

Временная сложность: $O(n)$.
Простой алгоритм: элементы проверяются по одному.
Линейный поиск: сканирование, сравнение, нахождение, остановка.

Бинарный поиск Анимация, демонстрирующая работу бинарного поиска

Временная сложность: $O(log\,n)$.
Эффективен, но требует отсортированного списка.
Бинарный поиск: деление, сравнение, исключение, повтор.

Заключение

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

Давайте потренируемся!

Основы информатики

Preparing Video For Download...