Подскажите где можно почитать теорию алгоритмов.
а количество операций от KТо есть нельзя даже по разу прочитать все элементы второго массива?
ага, и нельзя хранить первый массив. По-моему, от нас хотят рандомизатор
То есть нельзя даже по разу прочитать все элементы второго массива?по идее имелось ввиду: должно зависить меньше, чем N*K, т.е. не должно быть K операций на каждое число из N
Насколько я помню, там N > K. Ну и памяти и операций должно быть O(K) и O(N).
Когда-то решил эту задачку на собеседовании в абби.
Когда-то решил эту задачку на собеседовании в абби.
бор/trie
а что вы можете сказать по поводу сабжа )
Да, по поводу задачи, там действительно О(N) и О(К) должно быть.
я уже написал.
строишь из одного сэта бор, потом второй проверяешь по нему.
строишь из одного сэта бор, потом второй проверяешь по нему.
построение бора O(1)? Или все же N >> K?
/ == == ?
за O(K) потом поиск за O(N)
если можешь решить задачу быстрее чем за длину входа — расскажи.
если можешь решить задачу быстрее чем за длину входа — расскажи.
я просто посмотрел что по слову "бор" нихуя не гуглится
Вот я спрашиваю, trie - это перевод на общечеловеческий или отдельная идея? 
? бор это такой-же каламбур как и trie — типа и деревья и выбор есть =)
я просто посмотрел что по слову "бор" нихуя не гуглитсягуглится по «структура данных бор».
Я не говорю, что могу быстрее, в том-то и дело, уточняю условие, потому что без лишних предположений за O(N) действий сделать не выйдет.
каких предположений? очевидно если есть ограничения на объём памяти то её как-то надо использовать.
каких предположений? очевидно если есть ограничения на объём памяти то её как-то надо использовать.Бор строится за O(K поиск по нему тоже не константа, следовательно не получишь ты оценку на число операций как O(N). Ограничение N >> K (или K = o(N что однохуйственно) позволяет эту оценку получить. Я об этом.
>поиск по нему тоже не константа
мощность алфавита — константа. включи мозг.
мощность алфавита — константа. включи мозг.
мощность алфавита — константа. включи мозг.факт, тут не подумал. И вообще запутался, там N и K это длины самих строк. Ок. Все равно сам бор строится за O(K) и остальная часть моего рассуждения в силе.
сам бор строится за O(K)а проверка слов из второй строки за O(N)
а проверка слов из второй строки за O(N)Ну да. Итого O(N+K а не O(N как прошено было. Если же N>>K, то будет O(N только это я и спрашивал.
В условии в котором я решал было N > K т.е. O(N+K) = O(N). А N >> K не понятно зачем нужно.
В условии в котором я решал было N > K т.е. O(N+K) = O(N). А N >> K не понятно зачем нужно.Опять не день Бэкхема, действительно ни к чему =(
там похоже эту задачку сильно любят 
да и на этом форуме она не впервые всплывает
да и на этом форуме она не впервые всплываетОставить комментарий
ivan84
Подскажите пожалуйста хорошие книги или интернет сайты на которых можно почитать теорию составления алгоритмов.Если не сложно подскажите как составить алгоритм для следующей задачи:
Есть 2 строки длиной N и K. в этих строках записаны числа через пробелы. Числа могут быть очень длинными (например 100 значные). Надо составить алгоритм в котором будут выписываться все числа совпадающие в обеих строках и их порядковые номера в обеих строках. При этом количество выделяемой памяти не должно зависеть от N, а количество операций от K.
Заранее большое спасибо!