Об особенностях поиска информации в сети

Суббота, 27 Июня 2020 г. 16:21 + в цитатник

Qraizer: Неприятно, да, OpenGL? Эх, математики…
Алгоритм всё равно остался экспоненциальным, полиномиальным он будет, например, в такой форме:

template

type F(type n)

{

static std::deque A;

static const type minus_1 = static_cast(-1);

for(;;)

try

{

if (A.at(n-1) != -1) return A[n-1];

break;

}

catch(std::out_of_range&)

{

A.resize(n, minus_1);

}

if (n < 3) return 1;

if (A[n-2] == minus_1) A[n-2] = F(n-1);

A[n-1] = A[n-2] + A[n-3];

return A[n-1];

}

Только вы забыли, что сложность алгоритма – это качественное понятие,а не количественное.

Добавлено 27.06.20, 13:26
В данном случае количественной разницы нет.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833320