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

Кратко: линейный алгоритм — это такой алгоритм, который выполняется за время, пропорциональное размеру входных данных (n элементов). То есть время работы примерно пропорционально n: T(n) ≈ c·n + d, что записывается как O(n) в нотации БольшогоO. Пошаговое объяснение 1) Что такое «линейное время»? - Вход: набор данных размером n (например, массив из n чисел). - Линейный алгоритм делает фиксированное количество действий для каждого элемента входа. Он «проходит» по всем элементам один раз (или почти один раз). - Время работы растет пропорционально n. Увеличение размера входа в 2 раза почти удваивает время выполнения. 2) Как это записывают формально - Время работы: T(n) = a·n + b, где a и b — константы. - В нотации сложности: O(n) (линейный порядок). - Память: линейность времени не обязательно означает линейное использование памяти. Бывают линейные по времени и константной памяти (O(1) extra space), и линейно- по памяти (например, требует доп. массива на размере n). 3) Примеры линейных алгоритмов - Пример 1: Сумма элементов массива Псевдокод: sum = 0 for i от 1 до n: sum += a[i] вернуть sum Обоснование: нужно просуммировать каждый элемент массива, т.е. выполнить примерно n операций сложения. - Пример 2: Поиск максимального элемента в неотсортированном массиве max = a[1] for i от 2 до n: если a[i] > max: max = a[i] вернуть max Обоснование: каждый элемент массива приходится сравнить хотя бы с текущим максимумом. В худшем случае выполняются около n проверок. - Пример 3: Линейный поиск элемента x в массиве найден = false для i от 1 до n: если a[i] == x: найден = true; выйти вернуть найден Обоснование: в худшем случае приходится проверить все n элементов; в лучшем случае сразу на первом элементе. 4) Когда линейный алгоритм — оптимальный - Во многих задачах над неотсортированными данными невозможно узнать нужную характеристику быстрее, чем за O(n): например, сумма всех элементов, нахождение максимума, проверка наличия элемента в произвольном массиве. - Если вход можно отсортировать заранее, иногда можно решить задачу быстрее, но это уже другая задача: сортировка сама по себе стоит как минимум O(n log n) в общем случае, и линейный алгоритм не обязательно станет быстрее после сортировки. 5) Чем полезно помнить - Большое O не отсвечивает константы и скрытые затраты. Например, если переменная n очень мала, реальная скорость может быть другой, но в теории линейный алгоритм имеет O(n). - Время может быть линейным, а память — константной или линейной. Важно помнить разницу: O(n) по времени не обязательно равно O(n) по памяти. Если хочешь, могу привести ещё примеры или разобрать конкретную задачу и померить её временную сложность.