UntitledNikname, да, на вид тут на любой жадный алгоритм можно придумать вариант в котором он не сработает. а есть примеры, чтоб можно было свое решение проверить? и может ли быть ситуация когда решения нет (и будет ли достаточно в этом случае просто доказать что решения нет?) ?
а так на вид - MIP (элементарно) / динамическое программирование (на вид чуть больше телодвижений)
UntitledNikname, я правильно понимаю что у вас есть пулл чисел I, есть пул чисел Q. И нужно составить все числа в Q используя только то что есть в I (не нарушая при этом лимит по кол-ву использований) ?
stepa1411, я не уверен что я правильный человек чтоб отвечать на этот вопрос, но все-же что-то попробую подсказать.
по алгоритмам - возможно стоит попробовать Thomas Сormen "Algorithms unlocked" (ну русском она точно есть). Мне она в свое время показалась уж очень примитивной, но и мне уже далеко не 14 было. Будут советовать кнута - не ведитесь. Книги хорошие, но начинать с него будет уж совсем хардкорно.
именно по питону - ничего сказать не могу. У меня питон был наверно даже не в первой 10ке языков с которыми я работал, потому мое мнение будет сильно искажено. Подозреваю что можно брать того-же Лутца смело.
stepa1411, ... или к книгам. А они и сильно полезней, и сильно дешевле чем курсы (собственно полезность последних где-то около 0). И да, полно книг которые расчитаны на людей у которых питон - первый язык. + есть гарвардский cs50 прямо на ютубе на русском + платформы типа курсеры где можно запросить финансовую помощь которая покроет цену курса ( "я школьник и еще не зарабатываю деньги чтоб заплатить за курс" = достаточная причина чтоб эту помощь получить). А английский все-равно прийдется учить, так лучше раньше начать
2. Думаю это стоит уточнить прямо в теле вопроса т.к. просто "сравнить деревья" это в первую очередь про графы. подозреваю что в оригинальной формулировке звучало как-то "есть данные представлены в виде бинарного дерева. Нужно сравнить с другим деревом чтоб понять одинаковые ли в них данные". Тогда да, у вас наверно самое классическое решение для этой задачи. Я хотел написать что все прямо по кнуту, но потом пролистал вверх и увидел что действительно по кнуту. И решение вполне себе O(N).
1. не совсем, проблема с рекурсией не в том что это лишний вызов функции, а в том - что это создание копии всего контекста вызова каждый раз. Т.е. вместо того чтоб выделить 4 байта под счетчик 1 раз и пройтись по всем данным в цикле, вы будете выделять 4 байта на каждый рекурсивный вызов с новым значением счетчика. И все они будут висеть в памяти пока рекурсия не закончится. А теперь представьте что у вас там не 1 инт на 4 байта, а мегабайт данных. А программа работает в 16 потоков и уходит на глубину в несколько тысяч вызовов. Вот и выходит что она улетает в ООМ на рабочей машине, хотя реально переписав алгоритм можно было обойтись всего десятком мегабайт оперативки. Я могу ошибаться в нюансах работы именно питона, но +- эта проблема именно такая во всех языках без хвостовой оптимизации.
О нотация это аппроксимация от абстрактной сложности алгоритма. Она может быть для худшего/лучшего случая, она может быть по кол-ву перестановок/проходов/использованию памяти. Напирмер на примере вашего алгоритма O(N) - поиск по не сбалансированому дереву, O(logN) - поиск по сбалансированому дереву. Это позволяет грубо прикинуть эффективность алгоритма.
^ this. так-же добавлю что О - это аппроксимация. В случае с алгоритмом сортировки через вставку - сложность можно записать как (чесно стырино с вики, набирать ручками было лениво). Если откроете скобки получите что сложность = 1/2 * n^2 - 1/2 n. а O(1/2 * n^2 - 1/2 n) = О(n^2) т.к. откидываем константы
randomguyasking, можете распиливать на части пока любой кусок не станет достаточно мелким чтоб влезть в память (просто так распилить на 4 части нельзя, есть риск что разрежете группу). Тогда на первом шаге вы будете определять какой набор загрузить, а потом искать по нему. Можете распилить на очень много частей и разложить по папочкам в виде бинарного дерева. Тогда сначала вы будете использовать бинарный поиск чтоб найти в файловой системе нужный файл, а потом - чтоб найти в этом файле нужное значение. Можно вообще все хранить в одном файле, но рядом создать индекс который будет говорить с какой позиции и сколько значений надо загрузить в память. Главное вовремя остановится и не написать свою субд ;)
несколько странно, т.к. у питона есть https://github.com/renpy/renpy, которые писался специально под визуальные новеллы