Алгоритми опрацювання масивів: пошук найбільшого та найменшого значень

Пошук екстремальних значень (максимуму та мінімуму) — це фундаментальна задача програмування, яка лежить в основі аналізу даних, штучного інтелекту та систем автоматизації. У цій статті ми детально розглянемо теоретичні аспекти та практичну реалізацію цих алгоритмів.

Теоретична основа: Метод послідовного порівняння

Комп’ютер обробляє дані дискретно, тобто крок за кроком. Оскільки процесор не може «охопити поглядом» весь масив одночасно, він використовує ітераційний підхід. Найпоширенішим є алгоритм, який часто називають «методом чемпіона».

Основні етапи алгоритму:

1. Ініціалізація (Вибір еталона): Перед початком перебору необхідно визначити початкове значення для пошуку. Найбільш надійним методом є призначення першого елемента масиву (array[0]) як поточного максимуму або мінімуму.
   • Альтернатива: Використання системних констант (наприклад, від’ємна нескінченність для максимуму), проте вибір першого елемента є більш універсальним, оскільки він гарантує, що результат належатиме до самого набору даних.
2. Перебір (Цикл): Програма послідовно переглядає всі елементи масиву, починаючи з другого (індекс 1).
3. Порівняння та оновлення: На кожному кроці поточний елемент порівнюється з «чемпіоном».
   • При пошуку максимуму: якщо поточний > макс, то макс = поточний.
   • При пошуку мінімуму: якщо поточний < мін, то мін = поточний.

Складність та ефективність

Оскільки алгоритм вимагає перегляду кожного елемента масиву рівно один раз, його ефективність визначається наступними параметрами:

• Часова складність: $O(n)$, де $n$ — кількість елементів. Це оптимальна складність для невідсортованих даних.
• Пам’ять: $O(1)$ — для роботи алгоритму потрібна лише одна або дві додаткові змінні, незалежно від розміру вхідних даних.

---

Практична реалізація: Аналіз ігрових результатів

Уявімо систему, яка зберігає бали гравців. Нам потрібно знайти найкращий результат (максимум) та найгірший (мінімум), а також визначити, під якими номерами вони знаходяться.

Python

# Масив балів гравців
scores = [450, 120, 890, 530, 210, 890, 75]

# Ініціалізація
max_score = scores[0]
min_score = scores[0]
max_idx = 0
min_idx = 0

# Прохід по масиву
for i in range(1, len(scores)):
    # Логіка для максимуму
    if scores[i] > max_score:
        max_score = scores[i]
        max_idx = i
    
    # Логіка для мінімуму
    if scores[i] < min_score:
        min_score = scores[i]
        min_idx = i

print(f"Кращий результат: {max_score} (гравець №{max_idx + 1})")
print(f"Найгірший результат: {min_score} (гравець №{min_idx + 1})")

Домашнє завдання: Реалізуйте програму, яка знаходить різницю між максимальним та мінімальним елементами введеного користувачем масиву.