Практика алгоритмів на реальних прикладах

Концепції комп'ютерних наук

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

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

Сортування

Використовується, коли треба впорядкувати об'єкти

Завдання з реального життя:

  1. Онлайн-шопінг: сортування за ціною, рейтингом, популярністю.
  2. Календар: події за датою й часом.

Пошук

Використовується, коли треба знайти об'єкти

Завдання з реального життя:

  1. Онлайн-шопінг: пошук назви книжки.
  2. Підтримка клієнтів: пошук попередніх тікетів за іменем клієнта.
Концепції комп'ютерних наук

Алгоритми сортування: bubble sort vs quick sort

Bubble Sort Анімація, що показує роботу bubble sort

  • Bubble Sort: порівняти, поміняти місцями, повторити, прохід.
  • Часова складність: $O(n^2)$.
  • Уявіть онлайн-магазин з мільйонами товарів — зростає вибухово зі збільшенням каталогу.

Quick Sort Анімація, що показує роботу quick sort

  • Quick Sort: розділити, опорний елемент, впорядкувати, об'єднати.
  • Часова складність: O(n log n).
  • Уявіть онлайн-магазин з мільйонами товарів — масштабуються краще, коли каталог зростає.
Концепції комп'ютерних наук

Алгоритми пошуку: лінійний vs бінарний

Лінійний пошук Анімація, що показує роботу лінійного пошуку

  • Часова складність: $O(n)$.
  • Проста ідея: перевіряє кожен елемент послідовно.
  • Лінійний пошук: переглянути, порівняти, знайти, зупинитись.

Бінарний пошук Анімація, що показує роботу бінарного пошуку

  • Часова складність: $O(log\,n)$.
  • Ефективний, але потребує відсортованого списку.
  • Бінарний пошук: поділити, порівняти, відкинути, повторити.
Концепції комп'ютерних наук

Висновки

  • Bubble sort, quick sort, binary search, linear search
  • Quick Sort і Binary Search ефективніші для великих наборів даних.
  • Тепер у вас є відчуття, чому ефективність алгоритмів може покращити або зіпсувати взаємодію з технологіями.
Концепції комп'ютерних наук

Давайте потренуємось!

Концепції комп'ютерних наук

Preparing Video For Download...