Важность анализа алгоритмов проектирования (DAA) для хорошего программиста

По моему мнению, методы проектирования и анализа играют жизненно важную роль в мире программирования.

Для меня самым важным моментом является возможность показать, как мы можем внести определенные коррективы в наш код, чтобы сделать существующий алгоритм намного более эффективным с помощью определенных методов, таких как разделяй и властвуй, динамическое программирование и т. д. И возможность вносить улучшения в виде снижение вычислительной сложности, временной сложности и использования памяти может быть достигнуто только с помощью глубокого понимания существующих алгоритмов для различных сценариев.

Этот простой, но интригующий аргумент можно объяснить только с помощью нескольких примеров.

Возьмем пример методов сортировки. По умолчанию сортировка массива не является сложной задачей. Но самое интересное начинается, когда мы начинаем сравнивать каждый возможный алгоритм сортировки в разных ситуациях. Программист с не столь глубоким пониманием методов проектирования и анализа удовлетворится алгоритмом, имеющим временную сложность O(n). Но если вы знакомы с методами DAA, вы знаете, что существуют и другие алгоритмы с меньшей сложностью. Например, средняя временная сложность пузырьковой сортировки за O(n²), которая становится неэффективной для больших списков, но все же выполняет свою работу. Но для хорошего программиста вы бы выбрали более эффективные способы, такие как сортировка слиянием, имеющая O (nlogn) в качестве средней временной сложности. Кроме того, общий алгоритм можно улучшить, используя быструю сортировку, которая выполняется на месте и не требует дополнительного места для выполнения.

Кроме того, поскольку быстрая сортировка является алгоритмом сортировки на месте, она предпочтительнее для небольших массивов, а сортировка слиянием — для больших массивов. Итак, дьявол кроется в деталях. Настоящий программист анализирует все возможные варианты и выбирает наиболее эффективный. Следовательно, методы проектирования и анализа важны для того, чтобы стать хорошим программистом.

Мы будем рассматривать различные примеры, чтобы далее доказать это утверждение.

Проектирование и анализ также включают классы сложности, которые полезны во многих ситуациях. С помощью классов сложности мы можем эффективно разделить типы вычислительных задач, что дает нам отличное представление о том, как решать эти разные задачи на основе разделения, что полезно на практике.

Разделяя проблемы, мы получаем краткое представление о том, как нам следует к ним подходить.

Например, если проблема относится к классу NP, мы будем знать, что для ее решения с помощью недетерминированного алгоритма потребуется полиномиальное время. Таким образом, в этих сценариях было бы лучше следовать алгоритмам аппроксимации. Предположим, мы возьмем пример задачи оптимизации, где мы должны найти циклический маршрут с наименьшей стоимостью через все узлы взвешенного графа, который также известен как задача коммивояжера. Если мы стремимся найти точное решение вместо аппроксимации, это займет полиномиальное время, которого мы можем избежать, если заранее знаем, что оно принадлежит к классу сложности NP. Таким образом, это очень полезно во многих подобных ситуациях.

Существуют дополнительные классы сложности, такие как NP, как сложный, NP-полный, которые дополнительно разъясняют ситуации, когда проблемы находятся прямо рядом с границами NP и NP сложного.

Если мы возьмем другой пример, где, если проблема относится к классу R, поиск приближения даст нам худший результат, поскольку задачи, относящиеся к этому классу, могут быть решаемы, и для этого не требуется полиномиальное время. Таким образом, правильное знание различных классов может привести нас к оптимальному методу, который следует использовать для поиска решения с использованием наименьших возможных вычислительных ресурсов. Следовательно, на мой взгляд, даже если концепции класса сложности являются теоретическими, они очень часто используются в практических сценариях.

Есть много ситуаций, когда мы могли бы использовать разделяй и властвуй и динамическое программирование вместо обычного подхода, чтобы уменьшить временные сложности, что важно для любого программиста.

В разделе «разделяй и властвуй» проблема разбивается на две или несколько подзадач, которые рекурсивным образом похожи друг на друга. И этот процесс рекурсии продолжается по мере того, как проблема становится достаточно простой, чтобы ее можно было решить напрямую.

Принимая во внимание, что алгоритм динамического программирования также похож на метод «разделяй и властвуй». Он также разбивает проблему на несколько подзадач, но вместо повторного решения каждой подзадачи сохраняет предыдущее решение. Итак, для следующей подзадачи вместо пересчета всего решения просто берется ссылка из ранее решенной задачи и тем самым экономится время и вычислительные ресурсы. Таким образом, по сути, это улучшение концепции «разделяй и властвуй», поскольку она требует больше работы над подзадачами, что приводит к увеличению затрат времени. В то время как динамическое программирование решает подзадачи только один раз и сохраняет решение. Также разделяй и властвуй используется, когда подзадачи не зависят друг от друга, тогда как динамическое программирование, когда они зависимы. Таким образом, важно знать, какой алгоритм использовать в различных сценариях для получения оптимальных решений.

Если мы возьмем пример ряда Фибоначчи, в случае разделяй и властвуй мы просто используем рекурсивную функцию, чтобы найти сумму двух предыдущих значений. Но в динамическом программировании мы сохраняем ответ предыдущего вывода и сохраняем его в массиве для сравнения. И если подобный случай возникает в другой подзадаче, мы просто используем предыдущий вывод и, следовательно, экономим много времени. Таким образом, хороший программист, хорошо разбирающийся в DAA, лучше поймет, что динамическое программирование в этой ситуации лучше.

Еще одним жизненно важным преимуществом знания дизайна и анализа является использование алгоритма аппроксимации. Согласно науке, аппроксимация может означать использование более простой модели, а реальная модель, которая должна давать правильный результат, слишком сложна в использовании. Таким образом, в общем приближении используется для облегчения вычислений. Алгоритм аппроксимации возвращает решение каждой задачи оптимизации, которое, вероятно, близко к оптимальному, а не к эвристическому, которое может найти или не найти правильное решение. Это также предпочтительнее в некоторых сложных вычислительных задачах, потому что иногда найти почти оптимальное решение просто проще, чем найти точное решение, которое может потребовать много вычислительных ресурсов. Возьмем пример:

Предположим, что нам нужно решить NP-полную задачу. Как мы знаем, получить точное решение задач такого класса сложности было бы довольно сложно, так как для завершения недетерминированным решением потребовалось бы полиномиальное время. Таким образом, вместо того, чтобы искать лучшее решение, мы можем выбрать достойное решение, которое может быть в пределах 10% от оптимального и окажется более продуктивным. Тем не менее, сложность получения достойного приближения к различным решениям также довольно сложна, но это всегда лучший выбор для решения сложных вычислительных задач.

Как я уже сказал, чем больше примеров мы находим, тем яснее становится ответ. Работа хорошего программиста заключается не только в решении проблемы, но и в поиске наилучшего варианта в этом сценарии, что возможно только при глубоком понимании методов проектирования и анализа.

Следовательно, я полностью согласен с утверждением, что методы проектирования и анализа важны для того, чтобы стать хорошим программистом.