алгоритмы

[Авварон]

есть чего-нибудь почитать? А то был на собеседовании, не смог решить тамошние алгоритмические задачки... Только дома решил... Глубоко уязвлен собственной тупостью. Есть ли какая-нибудь книга (учебник 1го курса пойдет) где есть какие-л алгоритмические задачки? А то у нас не было по большому счету ничего.

[Alex_cs_gsp]

Алгоритмические задачки по программированию, или iq-шные, как в мелкософте спрашивают???

Если программирование, и задачки на простенькие алгоритмы (а не на такие как фрактальное сжатие изображений), то есть хорошая книга Г.Уорен "Алгоритмические трюки для программистов" (есть в сети). То, что для первых курсов, там сухая теория.

Есть еще Мозговой М.В. "Занимательное программирование" - там по чуть-чуть всех алгоритмов, и тоже не сухо. Примеры на Pascal и С++.

Если можешь выложи пожалуйста задачку, и скажи сколько на нее времени дали. Хочу свою тупость проверить.

[Авварон]

Задачка "в лоб" простейшая, а вот оптимизация по скорости/памяти хуже:)

[27.08.10 14:02:17] ABBAPOH: а 2я задачка - 2 строки длиной N и K, K <= N, в них записаны в символьном виде числа, разделены пробелами. Повторений внутри строки нет. Найти все числа, встречающиеся в обоих строках и напечатать из позицию. Длина чисел может быть большая (>100 знаков)
[27.08.10 14:02:32] ABBAPOH: сложность O(N), доп память O(K)

В условии точно не сказано что можно использовать, но я решал на чистом си. Мб если б мозг работал бы, там бы и решил (тк идея решения была уже там, но я не смог в мозгу просчитать сколько оно съест памяти... Показалось много:) надо было просто написать на сам деле)
давалось полчаса на эту, еще 1 совсем простенькую + еще общего плана на IQ, на них можно было забить

[Alex_cs_gsp]

Все, что быстро пришло в голову - это "смещать" меньший массив относительно большего и сравнивать символьно, но это не линейная сложность. А если хеши, то память не O(K) и также не линейная скорость.

[Igors]

ABBAPOH: а 2я задачка - 2 строки длиной N и K, K <= N, в них записаны в символьном виде числа, разделены пробелами. Повторений внутри строки нет. Найти все числа, встречающиеся в обоих строках и напечатать из позицию. Длина чисел может быть большая (>100 знаков)
[27.08.10 14:02:32] ABBAPOH: сложность O(N), доп память O(K)

Я спробовал (аттач), в полчаса конечно не уложился (ушел почти час). Отладка - конечно и конь не валялся. Нет ввода от командной строки. Ну и я-то был на своей машине (а не в гостях).  Так что расстраиваться особо нечего 

[Alex_cs_gsp]

ABBAPOH: а 2я задачка - 2 строки длиной N и K, K <= N, в них записаны в символьном виде числа, разделены пробелами. Повторений внутри строки нет. Найти все числа, встречающиеся в обоих строках и напечатать из позицию. Длина чисел может быть большая (>100 знаков)
[27.08.10 14:02:32] ABBAPOH: сложность O(N), доп память O(K)

Я спробовал (аттач), в полчаса конечно не уложился (ушел почти час). Отладка - конечно и конь не валялся. Нет ввода от командной строки. Ну и я-то был на своей машине (а не в гостях).  Так что расстраиваться особо нечего  

Что-то я не увидел линейного времени и линейной зависимости расхода памяти от строки K.

Код:

size_t total = num1 + num2;
	Token * token = new Token[total];

Получается память O(K+N)
А сложность алгоритма, как я понял у тебя может быть даже больше чем O((K+N)^2) - быстрая сортировка, уже не за линейное время + потом еще проход по объединенному массиву. Или нет?

[Авварон]

ну O(K+N) == O(max(K,N) == O(N) а решение ща гляну... мне тоже где-то час понадобился (30 минут там и полчаса дома на точный рассчет оценок).
Igors
Да, забыл уточнить - в задаче требование было что скорость не зависит от количества чисел. Но тем не менее, вы не укладываетесь по памяти

[Alex_cs_gsp]

 O(K+N) == O(max(K,N) == O(N))
Это как если будет выделено памяти K+N, а не max(K,N) ?

[Авварон]

O(x) == const*x => O(x+y) == c1*(x+y) <= c1*2*max(x,y) <= c2*max(x,y) == O(max(x,y))
это можно выделить памяти z*K но не z*N

[Alex_cs_gsp]

Что-то не совсем понял. Выложенный исходник при любом N и К всегда требует памяти N+K, следовательно и сложность алгоритма зависит как от N так и от K.

Если скорость не зависит от количества чисел, то это уже O(1), такое вообще возможно???

[Авварон]

если сложность зависит от 2х величин, то она зависит только от наибольшей их них (оценка сверху)
скорость должна зависеть не от количества чисел, а от длины строки (то есть она должна работать одинаково если строка из миллиона коротких чисел или из одного длинного - на N знаков)

[Igors]

Да, забыл уточнить - в задаче требование было что скорость не зависит от количества чисел. Но тем не менее, вы не укладываетесь по памяти

Ага, теперь дошло что от Вас хотели: что-то типа "сдвиг решетки". Находим совпадения сравнивая до K сначала начиная с 0-го элемента большей строки, затем с 1-го и так N - K раз. Да, так короче, но это ж издевательство над скоростью  

[Авварон]

нет, так вроде не хотели:) я имею решение удовлетворяющее условию, но имхо до него дойти сходу невозможно

[Alex_cs_gsp]

Любой алгоритм сортировки с попарным сравнением не лучше N*log(N). Может нужно создать пустой массив и инкрементировать  элементы соответствующие какому-то хитрому разбиению строк. Это можно сделать за линейное время, если известен диапазон чисел и они целые ( количество символов между пробелами). С памятью согласен, если с точностью до постоянного коэффициента (тут он не больше N-1).

[Авварон]

диапазон известен (от 0 и до 10 в степени N) числовое значение использовать бесполезно