Софтуерно Инженерство
Loading...
+ Нов въпрос
SophYO avatar SophYO 86 Точки

JavaFund/ TribonacciSequence

Здравейте!

Моля за малко съдействие.

С това решение: https://pastebin.com/F8arzhvN ми дава 90/ 100, като е -10 p, заради time limit.

Някой дали има идея къде е и как се получава преразхода на време?

Благодаря предварително!

0
Java Fundamentals
SophYO:
Стигнах до отговор :)
SophYO avatar SophYO 86 Точки

Та, след доста ровене и четене и след като стигнах до глава 10 от книгата на Св. Наков " Въведение в програмирането с Java", установих, че това е може би най- грешно взетото решение за решаване на тази задача, защото цитирам: " Това решение е интуитивно, кратко и лесно за разбиране. На пръв поглед изглежда, че това е чудесен пример за приложение на рекурсията. Истината е, че това е един от класическите примери за неподходящо използване на рекурсия. ..Ако зададем като стойност n = 100, изчисленията ще отнемат много дълго време (едва ли някой ще изчака толкова дълго, че да види резултата). Причината за това е, че подобна реализация е изключително неефективна. Всяко рекурсивно извикване води след себе си още две, при което дървото на извикванията расте експоненциално..Броят на стъпките за изчисление на fib(100) е от порядъка на 1.6 на степен 100 (това се доказва математически), докато при линейно решение е само 100.  
Проблемът произлиза от това, че се правят напълно излишни изчисления. Много от членовете на редицата се пресмятат многократно."

Ако някой също се е замислил за часовничето е та това е проблема. В книгата може да се открие и чудесно примерно решение на редицата на Фибоначи, което си е почти същото. :)


 

0