Алгоритмы и Структуры Данных. Урок 2: Мемоизация.

[@alishevN]

КУРС ПО GIT: www.udemy.com/course/git-alishev/?referralCode=71994763964B8E2E6A4E

[@ЮлияПавленко-щ7к]

Спасибо за курс! Самые понятные объяснения для тех, кто спал на лекциях в универе или их вообще не было :))

[@olegchumin6634]

Это как раз и есть образец элемента динамического программирования. Автору большой респект за уроки.

[@BoyarinLex]

Огромное спасибо за такие подробные разъяснения) Супергерой нашего времени 🔥Огромный жирный палец вверх 👍

[@АлександрМаркелов-ш3ж]

Наиль, как всегда прекрасно. Мой совет - если кто не понял как это работает - поставить число, допустим, 10 и пройтись дебагером - будет все наглядно - как проинициализируется массив -1 и как программа начнет проверять числа с числа n массива, опускаясь до 2 элемента и после этого заполняя массив до числа n

[@manOfPlanetEarth]

👍🏼

[@Дима-з3з7ц]

помогло, спасибо👍

[@igorkudryk2199]

Спасибо за качественные уроки!

[@hydrock9738]

Хорошие уроки! Спасибо.

[@yeson6581]

Уже на n = 93 пошли отрицательные числа, long закончился. Используйте BigInteger и не забывайте про метод сложения - add и valueOf(n).

[@denistalko6585]

Очень интересно, спасибо огромное!

[@pertshgalstyan6189]

Он вернулся 😎😎😎

[@Darmenw]

22:15 увеличив затрать память, снизим выполнение время выполнение

[@Tokamame]

На прошлом уроке подумал, что можно же было запоминать, например, n3 = 3. n4 = 5 и тд в массив. И дергать эти промежуточные числа из массива.

[@stanislav1125]

А так же можно использовать Option и еще красивее будет.

[@Andrzej3935]

Спасибо огромное!

[@alexanderostretsov2508]

Топовый мем)

[@mornier]

можно еще сократить память - использовать массив размерностью не n + 1, а три, и при каждой итерации сдвигать результаты. Рассмотренный Вами метод все равно сосчитает все значения чисел Фибоначи до n, а в результат все время выводится только одно число. Я про метод FibEffective

[@siegfried_dd]

Отлично!)

[@DimarikCanada]

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

[@АртемТит-в5ь]

это правда?

[@ХорхеРодригез]

Интересно, если в принципе фактор скорости выполнения программы можно определить "на глаз", то как понять насколько эффективно выделение памяти для того или иного подхода решения проблемы? Может есть плагины или отдельные методы для этого?

[@AroundIntellect]

Фактор памяти тоже определяется на глаз. Любая дополнительная переменная это О(1), массив и схожие структуры это О(n). Единственное помнить нужно, что нельзя считать за память выход функции. Пример по видео: Подаётся число n и требуется найти n-е число Фибоначчи. Автор для этого вводит целый массив, который равен О(n), возвращая только последний элемент массива, значит общие затраты памяти O(n). При этом, если бы по условию задачи требовалось вернуть все числа Фибоначчи до n, включительно, то этот же метод занимал бы О(1) по памяти, так как выходной массив не шёл бы в учёт, ведь без этого массива не получится вернуть массив, как бы это ни звучало. Так же хочу отметить, что О(n) по памяти для этой задачи не является оптимальным решением. Можно просто создать 2 переменные fib0 = 0 и fib1 = 1 перезаписывая их значение. То есть fib1 += fib 0; fib0 = fib1 - fib0. В конце необходимо вернуть fib1. Этот способ позволить уменьшить затраты памяти до константы, при этом скорость остаётся линейной.

[@footballlife9931]

спасибо!

[@bexcrypto]

зачем нужно было заполнять массив -1-ми, и не совсем понятно 18ая строка. Кто понял обьясните пожалуйста буду очень рад :)

[@andrsam3682]

Правильно ли я понимаю, что алгоритм быстрого преобразования Фурье - это дискретное преобразование Фурье с примененной мемоизацией?

[@maximbelousov1560]

В текущей реализации можно получить очень интересный результат при `n = 99 `=)

[@AndryMax]

очень странно, кто нибудь может объяснить такой результат? upd: а ну вроде потому что лонга не хватает, нужно использовать бигИнтеджер upd2: проверил с бигИнтеджер, всё идеально

[@witaliden]

long result = fibNaive(n-1, mem) + fibNaive(n-2, mem); Каким образом на данном этапе происходит сложение? Хоть тыкните, в какую сторону читать)

[@Qnoize]

ну наверное там, где стоит + ... ничего собственно в вычислении не поменялось, только результат присвоился переменной result

[@kr8525]

Здрастуйте, почему массив должен быть размером n+1, а не просто n?

[@alexander_brun]

Математики и программисты любят считать не с единицы, а с нуля. Поэтому с массивами и числами Фибоначчи нужно закладывать в размер этот первый нулевой. То есть десятый элемент будет по счету 11ый.

[@Darmenw]

22:15(1 первый урок) На первом уроке сказал увеличив затрать память, снизим выполнение время программа

[@ИгорьБирт-я2щ]

Не понимаю, почему массив создаем на 101 элемент [n+1] ???

[@pavelkravchenko7005]

Потому что при n = 0 в массиве должно лежать одно число - 0. Соответственно, при n = 1, их уже два - 0 и 1.

[@Darmenw]

22:15(1 первый урок) На первом уроке сказал увеличив затрать память, снизим выполнение время программа

[@kedr123]

Спасибо Вам за труды! Просьба выложить плейлист по алгоритмам на Python!)

[@Roma4086]

мемоизация - это и есть динамическое программировние?

[@alishevN]

похоже, но не совсем то же самое.

[@Roma4086]

@@alishevN а правильно ли сказать так, что при динамическом программировании мы решаем проблему рекурсивно, т.е. перебираем все возможные варианты и выбираем тот вариант, который дает манимум или максимум?

[@EEEppt]

Я так понимаю это по книжке грокаем алгоритмы? ))

[@agweprint27]

Наиль, скажи, а почему ты не поместил мем в метод фибнаив? Зачем он в мэйне, да и лишние аргументы у метода

[@alishevN]

Попробуй сделать так)

[@agweprint27]

@@alishevN всё, догнал) он же постоянно будет создавать заново при обращении :)

[@mikegrig903]

Как в этом так и в предыдущем уроке, 100е число фибоначи не получается, похоже не хватает длины long. Для интереса в цикле от 0 до 100 запусти!!! увидишь, что после 90 начинаются отрицательные числа!!!!

[@XIRON86]

Давайте создадим массив мемов)))

[@stanislav1125]

Зачем заполнять массив -1, чем плох != null ?

[@alexanderwicked8990]

Зачем заполнять массив -1? Потому что факториал всегда положителен, и -1 точно не пройдёт. А вы, прежде чем писать этот комментарий, сами хоть попробовали заполнить массив пустыми значениями через Arrays.fill? И как, всё хорошо, полёт нормальный?

[@andretiidook7022]

Лонг это не объект

[@stas4985]

@@andretiidook7022 ошибаешься малой,лонг с большой буквы это обьект

[@dressran3614]

герберт шилдт считает иначе)))@@stas4985

[@alexmakarov2504]

без массива еще в ~2 раза быстрее. long res = 0; long prev0 = 0; long prev1 = 1; for (int i = 2; i

[@AroundIntellect]

Слабо без переменной res?)

[@alexmakarov2504]

@@AroundIntellect Можно, просто у меня привычка всегда результат объявлять названием res и его возвращать. Компилятор это оптимизирует, а для меня удобнее.

[@AroundIntellect]

@@alexmakarov2504 В этом плане вопросов нет, читаемость бустит, а это стоит и 10 лишних переменных. Но лично я алгоритмы привык решать максимально оптимально, хоть и нечитаемо

[@alexmakarov2504]

@@AroundIntellect Да, согласен, тут не поспоришь, а я еще и плох в алгоритмах, к сожалению.

[@AroundIntellect]

@@alexmakarov2504 Кстати, достаточно больно решать алгоритмы на джаве... Толи дело питон, один кайф, 2-3 строчки и оптимальное решение готово 😂😅 Хотя программирование на джаве мне куда больше нравится

[@sashaosaula3325]

что то даже с дэбаггером не могу понять(((

[@Бардзо]

ничего непонятно,видос ток отбивает желание разбираться в теме(

[@Darmenw]

22:15(1 первый урок) long [ ] arr = long arr[n+1} На первом уроке сказал увеличив затрать память, чтобы снизить время выполнение программа @alishevN да ?