RNAfold Time сложность в пакете VinnaRNA

Может кто-нибудь сказать мне, какова сложность RNAfold алгоритм В VinnaRNA Пакет.
https://www.tbi.univie.ac.at/RNA/

Это Алго. присутствует в ViennaRNA-2.4.4\ViennaRNA-2.4.4\src\bin ,
Помоги мне.

0

Решение

В предоставленной вами ссылке есть эмпирический анализ времени выполнения. Вы можете увидеть линейное время вычислений на диаграмме.

Это означает, что вы можете написать (используя log для логарифма в базе 10 и вызова T временная сложность алгоритма)

   log(T(10^n)) = a.n + b                          for a and b to be read from the graph
=> T(10^n) = 10^(a.n + b) = C.10^(a.n)             with C constant
=> T(n) = T(10^(log(n)) = C.10^(a.log(n)) = C.n^a

Теперь, читая график, вы можете увидеть, что

  • T(length of RNA sequence = 1000) ~= 10^0 = 1
  • T(10000) ~= 10^2.6

Что даст вам приближение a ~= 2.6
Если вы хотите быть консервативным, вы можете связать a с 3 что приводит к сложности

T(n) = O(n^3)

куда n длина последовательности РНК в нуклеотидах.

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector