Technical
>> Development (Archive)
Страницы: 0 | (1) | 20 | показать все | след. страница
| | |
Kai : Re: Подскажите где можно почитать теорию алгоритмов.
[re:MadSpirit] 02.03.2009 21:13 | Reply | Edit |
| 9 |
Quote:
а количество операций от K
То есть нельзя даже по разу прочитать все элементы второго массива?
| |
ayvango
[re:Kai] 02.03.2009 21:17 | Reply | Edit |
| -1 |
ага, и нельзя хранить первый массив. По-моему, от нас хотят рандомизатор
| |
DarkGray
[re:Kai] 02.03.2009 21:30 | Reply | Edit |
| 0 |
Quote:
То есть нельзя даже по разу прочитать все элементы второго массива?
по идее имелось ввиду: должно зависить меньше, чем N*K, т.е. не должно быть K операций на каждое число из N
| |
porcupine
[re:DarkGray] 02.03.2009 21:46 | Reply | Edit |
| 0 |
Насколько я помню, там N > K. Ну и памяти и операций должно быть O(K) и O(N).
Когда-то решил эту задачку на собеседовании в абби.
| |
blind
[re:MadSpirit] 02.03.2009 21:50 | Reply | Edit |
| 2 |
бор/trie
| |
MadSpirit
[re:porcupine] 02.03.2009 22:27 | Reply | Edit |
| -2 |
а что вы можете сказать по поводу сабжа )
| |
MadSpirit
[re:MadSpirit] 03.03.2009 00:12 | Reply | Edit |
| 0 |
Да, по поводу задачи, там действительно О(N) и О(К) должно быть.
| |
blind
[re:MadSpirit] 03.03.2009 07:51 | Reply | Edit |
| 1 |
я уже написал.
строишь из одного сэта бор, потом второй проверяешь по нему.
| |
unkulunkulu
[re:blind] 03.03.2009 08:38 | Reply | Edit |
| 0 |
построение бора O(1)? Или все же N >> K?
| |
Kai
[re:blind] 03.03.2009 09:02 | Reply | Edit |
| 0 |
/ == == ?
| |
blind
[re:unkulunkulu] 03.03.2009 09:03 | Reply | Edit |
| 0 |
за O(K) потом поиск за O(N)
если можешь решить задачу быстрее чем за длину входа - расскажи.
| |
blind
[re:Kai] 03.03.2009 09:03 | Reply | Edit |
| 1 |
я просто посмотрел что по слову "бор" нихуя не гуглится
| |
Kai
[re:blind] 03.03.2009 09:05 | Reply | Edit |
| 1 |
Вот я спрашиваю, trie - это перевод на общечеловеческий или отдельная идея? 
| |
blind
[re:Kai] 03.03.2009 09:07 | Reply | Edit |
| 0 |
?? бор это такой-же каламбур как и trie - типа и деревья и выбор есть =)
| |
unkulunkulu
[re:blind] 03.03.2009 09:21 | Reply | Edit |
| 0 |
Quote:
я просто посмотрел что по слову "бор" нихуя не гуглится
гуглится по 'структура данных бор'.
Я не говорю, что могу быстрее, в том-то и дело, уточняю условие, потому что без лишних предположений за O(N) действий сделать не выйдет.
| |
blind
[re:unkulunkulu] 03.03.2009 09:24 | Reply | Edit |
| 0 |
каких предположений? очевидно если есть ограничения на объем памяти то ее как-то надо использовать.
| |
unkulunkulu
[re:blind] 03.03.2009 09:43 | Reply | Edit |
| 0 |
Quote:
каких предположений? очевидно если есть ограничения на объем памяти то ее как-то надо использовать.
Бор строится за O(K), поиск по нему тоже не константа, следовательно не получишь ты оценку на число операций как O(N). Ограничение N >> K (или K = o(N), что однохуйственно) позволяет эту оценку получить. Я об этом.
| |
blind
[re:unkulunkulu] 03.03.2009 10:09 | Reply | Edit |
| 1 |
>поиск по нему тоже не константа
мощность алфавита - константа. включи мозг.
| |
unkulunkulu
[re:blind] 03.03.2009 10:47 | Reply | Edit |
| 0 |
Quote:
мощность алфавита - константа. включи мозг.
факт, тут не подумал. И вообще запутался, там N и K это длины самих строк. Ок. Все равно сам бор строится за O(K) и остальная часть моего рассуждения в силе.
| |
blind
[re:unkulunkulu] 03.03.2009 11:02 | Reply | Edit |
| 0 |
В ответ на:
сам бор строится за O(K)
а проверка слов из второй строки за O(N)
| |
| Top | след. страница |