Алгоритмы и их эффективность
💻 Информатика · 10 класс
Алгоритмы и их эффективность
Алгоритм — конечная последовательность точных команд, ведущая от исходных данных к результату. В 10 классе акцент смещается с самого понятия на эффективность: одну задачу можно решить разными алгоритмами, и важно выбрать тот, что работает быстрее и экономнее. Эффективность оценивают по затратам времени (число операций) и памяти при росте объёма входных данных n.
Сложность алгоритма
Вычислительная сложность показывает, как растёт число операций с увеличением n. Её записывают через скорость роста. Если для массива из n элементов алгоритм делает порядка n действий — это линейная сложность; если n² — квадратичная; если порядка log n — логарифмическая (очень быстрая).
| Сложность | Рост операций | Пример алгоритма |
|---|---|---|
| Логарифмическая | log n | Двоичный поиск |
| Линейная | n | Линейный поиск, сумма массива |
| Квадратичная | n² | Сортировка «пузырьком» |
Поиск элемента
Линейный поиск перебирает элементы подряд, пока не найдёт нужный, — в худшем случае n сравнений. Если массив отсортирован, работает двоичный (бинарный) поиск: он сравнивает искомое со средним элементом и каждый раз отбрасывает половину диапазона.
лево = 1, право = n
пока лево <= право
середина = (лево + право) / 2
если A[середина] = x → нашли, стоп
если A[середина] < x → лево = середина + 1
иначе → право = середина - 1
В массиве из 1000 элементов линейный поиск может сделать 1000 сравнений, а двоичный — около 10, ведь каждый шаг сокращает область вдвое.
Сортировка
Сортировка пузырьком многократно проходит по массиву, меняя местами соседние элементы, если они стоят в неверном порядке; за каждый проход наибольший элемент «всплывает» в конец. Это наглядный, но медленный метод сложности n². Существуют более быстрые сортировки (слиянием, быстрая) со сложностью порядка n·log n.
для i от 1 до n-1
для j от 1 до n-i
если A[j] > A[j+1]
то поменять местами A[j] и A[j+1]
Здесь два вложенных цикла дают как раз порядок n² сравнений. На массиве из 10 элементов это около 100 операций, а на 1000 — уже около миллиона: вот почему квадратичные алгоритмы плохо подходят для больших данных.
Почему сложность важна
Разница в сложности проявляется именно с ростом n. При n = 10 квадратичный и линейный алгоритмы почти неотличимы, но при n = 1 000 000 квадратичный потребует триллион операций и «зависнет», а логарифмический управится за два десятка шагов. Поэтому при работе с большими объёмами данных выбор эффективного алгоритма важнее мощности компьютера.
Практическое правило. Двоичный поиск применим только к упорядоченному массиву — на неотсортированных данных он даст неверный ответ. Прежде чем ускорять поиск, оцените, не дороже ли обойдётся сортировка. Для маленьких n разница в сложности почти незаметна, она важна на больших данных.
Кратко о главном
- Эффективность алгоритма оценивают по затратам времени и памяти при росте n.
- Сложность бывает логарифмической, линейной, квадратичной и др.
- Линейный поиск работает всегда, двоичный — только в отсортированном массиве, но гораздо быстрее.
- Сортировка пузырьком проста, но медленна (n²); есть методы быстрее.
- Выбор алгоритма особенно важен при больших объёмах данных.