Выравнивание последовательностей в линейном пространстве по принципу «разделяй и властвуй»

В предыдущем разделе был рассмотрен процесс вычисления оптимального вы- равнивания между двумя строкамиX и Y длины m и n соответственно. Построение двумерного массива m χ n оптимальных решений подзадач, OPT(·, ), оказалось эквивалентным построению графа GXY с mn узлами, образующими решетку, и по- иску пути наименьшей стоимости между противоположными углами.
В каждом из этих способов формулировки алгоритма динамического программирования время выполнения равно O(mn), потому что значение каждой из mn ячеек массива OPT определяется за постоянное время; затраты памяти также равны O(mn), потому что в них доминируют затраты на хранение массива (или графа GXY).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Выравнивание последовательностей в линейном пространстве по принципу «разделяй и властвуй»:

  1. ПЯТАЯ СТАДИЯ: Выравнивание принципов
  2. ИГНОРИРУЙТЕ ЛИНЕЙНЫЕ ПРЕДСКАЗАНИЯ И ИЗБЕГАЙТЕ ЛИНЕЙНЫХ ВЫВОДОВ! ВЕРЬТЕ СВОЕМУ СЕРДЦУ!
  3. Понятие коммуникации как методологический принцип построения гносеологической конструкции социокультурного пространства города
  4. Существуют три стратегических принципа последовательности задаваемых вопросов — хронологический, логический, импровизационный. В первом случае в центре внимания — события; во втором — предметы общественного обсуждения; в третьем — человеческий характер.
  5. СТАДИЯ ЧЕТВЕРТАЯ: Выравнивание систем
  6. ТРЕТЬЯ СТАДИЯ: Выравнивание отношений
  7. Разделяющее мышление
  8. 2. Выравнивание энергетических систем целителя, пациента и наставников.
  9. Линейно-функциональные структуры.
  10. Разделяющее двойственное мышление
  11. Разделяющее мышление.
  12. Характеристики современного разделяющего ума-эго
  13. Линейный и нелинейный умы