Подскажите где можно почитать теорию алгоритмов. - Public forum of MSU united student networks

Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.snto-msu.net/showflat.php?Number=8407046&src=arc&showlite=
Дата изменения: Unknown
Дата индексирования: Tue Apr 12 06:25:28 2016
Кодировка: Windows-1251

Подскажите где можно почитать теорию алгоритмов. - Public forum of MSU united student networks

Root \| Google \| Yandex \| Mail.ru \| Kommersant \| Afisha \| LAN Support

Список форумов | Поиск | Новый пользователь | Вход | Кто в онлайне | FAQ | Пользователи

Technical >> Development (Archive)

Страницы: 0 | 20 | показать все | след. страница

addict

Рег.: 17.09.2005

Сообщений: 616

Из: Москва

Рейтинг: -9

Подскажите где можно почитать теорию алгоритмов.
02.03.2009 21:06

Подскажите пожалуйста хорошие книги или интернет сайты на которых можно почитать теорию составления алгоритмов.

Если не сложно подскажите как составить алгоритм для следующей задачи:
Есть 2 строки длиной N и K. в этих строках записаны числа через пробелы. Числа могут быть очень длинными (например 100 значные). Надо составить алгоритм в котором будут выписываться все числа совпадающие в обеих строках и их порядковые номера в обеих строках. При этом количество выделяемой памяти не должно зависеть от N, а количество операций от K.

Заранее большое спасибо!

Рег.: 25.10.2002

Сообщений: 8251

Рейтинг: 818

Re: Подскажите где можно почитать теорию алгоритмов. [re: MadSpirit]
02.03.2009 21:13

9

Quote:

а количество операций от K

То есть нельзя даже по разу прочитать все элементы второго массива?

ушастый

Рег.: 10.01.2006

Сообщений: 27731

Из: Воронеж

Рейтинг: 11832

Re: Подскажите где можно почитать теорию алгоритмов. [re: Kai]
02.03.2009 21:17

-1

ага, и нельзя хранить первый массив. По-моему, от нас хотят рандомизатор

Сеть темна и полна ужасов

Модератор

Carpal Tunnel

Рег.: 30.09.2002

Сообщений: 31410

Рейтинг: 8951

Re: Подскажите где можно почитать теорию алгоритмов. [re: Kai]
02.03.2009 21:30

Quote:

То есть нельзя даже по разу прочитать все элементы второго массива?

по идее имелось ввиду: должно зависить меньше, чем N*K, т.е. не должно быть K операций на каждое число из N

Carpal Tunnel

Рег.: 09.09.2008

Сообщений: 6598

Рейтинг: 7627

Re: Подскажите где можно почитать теорию алгоритмов. [re: DarkGray]
02.03.2009 21:46

Насколько я помню, там N > K. Ну и памяти и операций должно быть O(K) и O(N).
Когда-то решил эту задачку на собеседовании в абби.

And then my master flew to the moon in a rocket of flamin' cheese! I like cheese!

still alive

Рег.: 16.01.2004

Сообщений: 23127

Из: Хамовники

Рейтинг: 16481

Re: Подскажите где можно почитать теорию алгоритмов. [re: MadSpirit]
02.03.2009 21:50

2

бор/trie

13/37 =)

addict

Рег.: 17.09.2005

Сообщений: 616

Из: Москва

Рейтинг: -9

Re: Подскажите где можно почитать теорию алгоритмов. [re: porcupine]
02.03.2009 22:27

-2

а что вы можете сказать по поводу сабжа )

addict

Рег.: 17.09.2005

Сообщений: 616

Из: Москва

Рейтинг: -9

Re: Подскажите где можно почитать теорию алгоритмов. [re: MadSpirit]
03.03.2009 00:12

Да, по поводу задачи, там действительно О(N) и О(К) должно быть.

still alive

Рег.: 16.01.2004

Сообщений: 23127

Из: Хамовники

Рейтинг: 16481

Re: Подскажите где можно почитать теорию алгоритмов. [re: MadSpirit]
03.03.2009 07:51

1

я уже написал.
строишь из одного сэта бор, потом второй проверяешь по нему.

13/37 =)

unkulunkulunkulu

Рег.: 12.11.2006

Сообщений: 18453

Из: 13000

Рейтинг: 11759

Re: Подскажите где можно почитать теорию алгоритмов. [re: blind]
03.03.2009 08:38

построение бора O(1)? Или все же N >> K?

Рег.: 25.10.2002

Сообщений: 8251

Рейтинг: 818

Re: Подскажите где можно почитать теорию алгоритмов. [re: blind]
03.03.2009 09:02

/ == == ?

still alive

Рег.: 16.01.2004

Сообщений: 23127

Из: Хамовники

Рейтинг: 16481

Re: Подскажите где можно почитать теорию алгоритмов. [re: unkulunkulu]
03.03.2009 09:03

за O(K) потом поиск за O(N)
если можешь решить задачу быстрее чем за длину входа - расскажи.

13/37 =)

still alive

Рег.: 16.01.2004

Сообщений: 23127

Из: Хамовники

Рейтинг: 16481

Re: Подскажите где можно почитать теорию алгоритмов. [re: Kai]
03.03.2009 09:03

1

я просто посмотрел что по слову "бор" нихуя не гуглится

13/37 =)

Рег.: 25.10.2002

Сообщений: 8251

Рейтинг: 818

Re: Подскажите где можно почитать теорию алгоритмов. [re: blind]
03.03.2009 09:05

1

Вот я спрашиваю, trie - это перевод на общечеловеческий или отдельная идея? :grin:

:grin:

still alive

Рег.: 16.01.2004

Сообщений: 23127

Из: Хамовники

Рейтинг: 16481

Re: Подскажите где можно почитать теорию алгоритмов. [re: Kai]
03.03.2009 09:07

?? бор это такой-же каламбур как и trie - типа и деревья и выбор есть =)

13/37 =)

unkulunkulunkulu

Рег.: 12.11.2006

Сообщений: 18453

Из: 13000

Рейтинг: 11759

Re: Подскажите где можно почитать теорию алгоритмов. [re: blind]
03.03.2009 09:21

Quote:

я просто посмотрел что по слову "бор" нихуя не гуглится

гуглится по 'структура данных бор'.

Я не говорю, что могу быстрее, в том-то и дело, уточняю условие, потому что без лишних предположений за O(N) действий сделать не выйдет.

still alive

Рег.: 16.01.2004

Сообщений: 23127

Из: Хамовники

Рейтинг: 16481

Re: Подскажите где можно почитать теорию алгоритмов. [re: unkulunkulu]
03.03.2009 09:24

каких предположений? очевидно если есть ограничения на объем памяти то ее как-то надо использовать.

13/37 =)

unkulunkulunkulu

Рег.: 12.11.2006

Сообщений: 18453

Из: 13000

Рейтинг: 11759

Re: Подскажите где можно почитать теорию алгоритмов. [re: blind]
03.03.2009 09:43

Quote:

каких предположений? очевидно если есть ограничения на объем памяти то ее как-то надо использовать.

Бор строится за O(K), поиск по нему тоже не константа, следовательно не получишь ты оценку на число операций как O(N). Ограничение N >> K (или K = o(N), что однохуйственно) позволяет эту оценку получить. Я об этом.

still alive

Рег.: 16.01.2004

Сообщений: 23127

Из: Хамовники

Рейтинг: 16481

Re: Подскажите где можно почитать теорию алгоритмов. [re: unkulunkulu]
03.03.2009 10:09

1

>поиск по нему тоже не константа
мощность алфавита - константа. включи мозг.

13/37 =)

unkulunkulunkulu

Рег.: 12.11.2006

Сообщений: 18453

Из: 13000

Рейтинг: 11759

Re: Подскажите где можно почитать теорию алгоритмов. [re: blind]
03.03.2009 10:47

Quote:

мощность алфавита - константа. включи мозг.

факт, тут не подумал. И вообще запутался, там N и K это длины самих строк. Ок. Все равно сам бор строится за O(K) и остальная часть моего рассуждения в силе.

Страницы: 0 | 20 | показать все | след. страница

Technical >> Development (Archive)

Дополнительная информация
1 зарегистрированных и 0 анонимных пользователей просматривают этот форум. Модераторы: DarkGray Печать темы >>	Права Вы можете создавать новые темы Вы можете отвечать на сообщения HTML отключен UBBCode включен	Рейтинг: Просмотров темы:
		Переход в