Расположите основные классы алгоритмической сложности по возрастанию (от наилучшей к наихудшей) и приведите примеры кода на Go для некоторых из них.

Основные классы алгоритмической сложности в порядке возрастания эффективности (от лучшей к худшей) выглядят так:

O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!)

Объяснение и примеры на Go

1. O(1) — Константное время
Время выполнения не зависит от размера входных данных.

// Получение элемента из слайса по индексу
// не зависит от количества элементов в `arr`.
func getFirstElement(arr []int) int {
    if len(arr) == 0 {
        return -1 // или вернуть ошибку
    }
    return arr[0]
}

2. O(log n) — Логарифмическое время
Время выполнения растет логарифмически с увеличением размера данных. Обычно это алгоритмы, которые на каждом шаге отбрасывают половину данных.

// Бинарный поиск в отсортированном массиве.
func binarySearch(arr []int, target int) bool {
    low, high := 0, len(arr)-1
    for low <= high {
        mid := low + (high-low)/2 // Безопасное вычисление середины
        if arr[mid] == target {
            return true
        }
        if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return false
}

3. O(n) — Линейное время
Время выполнения прямо пропорционально размеру входных данных. Алгоритму нужно "просмотреть" каждый элемент один раз.

// Линейный поиск элемента в массиве.
func findValue(arr []int, target int) bool {
    for _, v := range arr {
        if v == target {
            return true
        }
    }
    return false
}

4. O(n log n) — Линейно-логарифмическое время
Это "золотой стандарт" для алгоритмов сортировки, основанных на сравнениях. Примеры: сортировка слиянием (Merge Sort), быстрая сортировка (Quick Sort).

// В стандартной библиотеке Go функция sort.Ints
// использует гибридный алгоритм (IntroSort), 
// который в среднем имеет сложность O(n log n).

import "sort"

func sortArray(arr []int) {
    sort.Ints(arr)
}

5. O(n²) — Квадратичное время
Время выполнения растет пропорционально квадрату размера данных. Часто встречается во вложенных циклах, где оба цикла итерируются по одному и тому же набору данных.

// Проверка на наличие дубликатов с помощью вложенных циклов.
func hasDuplicates(arr []int) bool {
    n := len(arr)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if arr[i] == arr[j] {
                return true
            }
        }
    }
    return false
}

6. O(2ⁿ) — Экспоненциальное время
Время выполнения удваивается с каждым новым элементом. Такие алгоритмы очень медленные и применимы только для малых n. Пример: рекурсивное вычисление чисел Фибоначчи без мемоизации.

7. O(n!) — Факториальное время
Время выполнения растет с факториальной скоростью. Это самые медленные алгоритмы. Пример: решение задачи коммивояжера методом полного перебора всех возможных маршрутов.