Что такое алгоритм?

Что такое алгоритм?

Алгоритм — это чётко определённая последовательность шагов (инструкций), которая решает конкретную задачу за конечное время. Это фундаментальная концепция компьютерной науки и программирования.

Определение

Алгоритм — это:

• Детерминированный: для одного входа всегда один выход
• Конечный: завершается за конечное число шагов
• Эффективный: решает задачу оптимально
• Правильный: даёт корректный результат

Примеры базовых алгоритмов:

1. Поиск максимума в списке

def find_max(arr):
    """Алгоритм поиска максимума O(n)"""
    if not arr:
        return None
    max_val = arr[0]
    for num in arr[1:]:
        if num > max_val:
            max_val = num
    return max_val

print(find_max([3, 7, 2, 9, 1]))  # 9

2. Сортировка (Bubble Sort)

def bubble_sort(arr):
    """Простая сортировка пузырьком O(n²)"""
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))  # [11, 12, 22, 25, 34, 64, 90]

3. Бинарный поиск

def binary_search(arr, target):
    """Поиск элемента в отсортированном массиве O(log n)"""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # не найден

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3

Характеристики алгоритмов:

1. Временная сложность (Time Complexity) Как быстро растёт время выполнения с увеличением входных данных:

# O(1) — константная сложность
def get_first_element(arr):
    return arr[0]

# O(n) — линейная
def find_element(arr, target):
    for item in arr:
        if item == target:
            return True

# O(n²) — квадратичная
def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr) - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# O(log n) — логарифмическая
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

# O(n log n) — логлинейная (оптимальная сортировка)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

2. Пространственная сложность (Space Complexity) Сколько дополнительной памяти требует алгоритм:

# O(1) — постоянная память
def sum_array(arr):
    total = 0  # одна переменная
    for num in arr:
        total += num
    return total

# O(n) — линейная память
def copy_array(arr):
    new_arr = arr.copy()  # новый массив того же размера
    return new_arr

# O(log n) — логарифмическая (рекурсивные вызовы)
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

Big O Нотация — сравнение сложностей:

O(1)     < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
бестый                                                    худший

Классические алгоритмы по областям:

Сортировка:

• Quick Sort: O(n log n) в среднем
• Merge Sort: O(n log n) гарантировано
• Heap Sort: O(n log n)

Поиск:

• Linear Search: O(n)
• Binary Search: O(log n)
• Hash Table Lookup: O(1) в среднем

Графы:

• BFS/DFS: O(V + E)
• Dijkstra: O((V + E) log V)
• Floyd-Warshall: O(V³)

Динамическое программирование:

• Fibonacci: O(n) с DP (vs O(2ⁿ) наивное)
• Knapsack: O(n × w)

Разработка и анализ алгоритма:

1. Понять задачу: чётко определить вход и выход
2. Разработать: описать шаги решения
3. Доказать корректность: почему алгоритм работает
4. Анализ сложности: время и память
5. Оптимизация: улучшить если нужно
6. Реализация: написать код
7. Тестирование: проверить на примерах

Практический совет для собеседования:

Когда решаете задачу:

• Сначала напишите простое решение O(n²)
• Затем оптимизируйте до O(n log n) или O(n)
• Обсуждайте trade-offs памяти и скорости
• Рассказывайте о сложности вслух