Обозначение Big-O: использование приближения и эвристики
Задачи оптимизации, такие как задача коммивояжёра (далее будем называть её TSP), могут иметь только одно точное решение и несколько решений, близких к оптимальным. Алгоритмы, которые находят почти оптимальные решения с помощью аппроксимации и эвристики, обычно принадлежат к лучшему классу O(n), чем точный алгоритм.
Например, в алгоритме TSP коммивояжёр, прибыв в один из городов, указанных в повестке дня, просто выбирает ближайший непосещенный город в качестве следующего пункта назначения, пока не будут посещены все города.
В среднем путь, полученный в результате этой стратегии, на 25% длиннее, чем результат точного алгоритма, в то время как алгоритму ближайшего соседа требуется только O(n^2) время.
Другие стратегии включают оптимизацию муравьиной колонии, моделирование отжига и генетические алгоритмы.
Может ли параллельное выполнение достичь лучшего класса сложности?
Учитывая, что горутины могут выполняться параллельно (при условии, что доступно более одного (физического) ядра ЦП), на ум приходит вопрос: может ли параллельная версия алгоритма принадлежать к лучшему классу сложности, чем исходный последовательный алгоритм?
Например, можно ли решить TSP в O(n^2), а не в O(2^n) при использовании точного алгоритма и без эвристики? К сожалению, нет.
Чтобы объяснить это, мы даже не погружаемся в теорию сложности. Нам просто нужно взглянуть на аппаратное обеспечение: два ядра ЦП могут обеспечить максимум двойную скорость, три могут обеспечить тройную скорость, и так далее. Таким образом, добавление ядер ЦП ускоряет выполнение только на постоянный коэффициент, а, как мы видели во введении, постоянные коэффициенты не имеют значения, когда речь идет о классах временной сложности.
Подводя итог, стоит отметить, что временная сложность и классы Big-O могут показаться утомительными вещами, но они чрезвычайно полезны для прогнозирования поведения кода при увеличении размера входных данных. За всем этим стоит пропасть теории, но этого базового набора классов сложности должно хватить для повседневного использования.
С оригиналом статьи ты можешь ознакомиться по ссылке.
Рекомендуем также ознакомиться с дополнительными материалами по теме: