Здравствуйте, elmal, Вы писали:

E>На задачки тоже натаскаться особой сложности не представляет. Тем более задачки эти типовые до ужаса. Нет, именно спеца, который пошел на остаточных знаниях вы возможно на задачах и срежете, так как он может их не очень уверенно решать. Но того, кто к собеседованию целенаправленно готовился — хрен задачками срежешь .

Да ладно, вот random sort это наша задачка и что-то я не наблюдаю толпы натаскавшихся. У меня есть такие же вселые задачки на SQL, многопоточность, архитектуру, вычгем, но и там натаскавшихся не наблюдается. Возможно, они все свалили в микрософт и гугл с амазоном.

Целенаправленно можно готовиться только к тупым задачкам типа сортировки люков или разворота списков, в нормальных же конторах задачи берут из практики, из числа тех, на которых обломал зубы не один сотрудник. И как раз спец который 10 лет такие проблемы решал их с легкостью разберет, а быдлокодер на остаточных знаниях об О-нотации с первого курса срежется, независимо от того готовился он или нет.

Здравствуйте, Константин, Вы писали:

К>Тоже мне, бином Ньютона. В худшем случае алгоритм не сойдётся, а вот в описании нет критерия остановки.

Вообще-то сойдется на бесконечности, это элементарно доказывается. А вот критерия остановки нет потому что у бесконечных итеративных алгоритмов его в принципе не бывает, что, однако, совcем не мешает оценивать трудоемкость, зато замечательно ставит студиозусов в тупик.

Здравствуйте, Аноним, Вы писали:

А>Да ладно, вот random sort это наша задачка и что-то я не наблюдаю толпы натаскавшихся. У меня есть такие же вселые задачки на SQL, многопоточность, архитектуру, вычгем, но и там натаскавшихся не наблюдается. Возможно, они все свалили в микрософт и гугл с амазоном.
Прям таки ваша задача. Это называется богосорт, вообще то, идея стара как мир.

А>Целенаправленно можно готовиться только к тупым задачкам типа сортировки люков или разворота списков, в нормальных же конторах задачи берут из практики, из числа тех, на которых обломал зубы не один сотрудник.
Ух ты . Оказывается есть конторы, которые богосорт используют на практике, не знал . А относительно практики — это меня умиляет. Берется задача, над которой сам лично провозился больше дня, и от кандидата ожидается, что он за 15 минут мгновенно найдет в чем подвох . Боюсь к вам только мыщьх пройдет, ибо он за 5 минут придумывает решение нерешенных проблем. Но во первых, он все равно натаскивался в свое время на задачи, а во вторых, у него такса будет поболее 150 тысяч .

Здравствуйте, Аноним, Вы писали:

К>>Тоже мне, бином Ньютона. В худшем случае алгоритм не сойдётся, а вот в описании нет критерия остановки.
А>Вообще-то сойдется на бесконечности, это элементарно доказывается.
Да ладно. В худшем случае алгоритм не сходится: ну не повезло нам — "монетка" всегда просит переставить элементы 1 и 2.

А>А вот критерия остановки нет потому что у бесконечных итеративных алгоритмов его в принципе не бывает, что, однако, совcем не мешает оценивать трудоемкость, зато замечательно ставит студиозусов в тупик.

Договаривайте до конца, что вам нужно от алгоритма:
— массив отсортирован с заданной вероятностью p. Критерий остановки — число шагов (зависит от вероятности).
— массив "вроде отсортирован". 100500 шагов без изменений массива — пора остановиться
— массив отстортирован. Критерий остановки — проверка на сортированность на каждом шаге (что уж мелочиться )

Здравствуйте, Аноним, Вы писали:

А>Вообще-то сойдется на бесконечности, это элементарно доказывается.

Что означает "на бесконечности" в контексте обсуждения сложности худшего случая?

А>А вот критерия остановки нет потому что у бесконечных итеративных алгоритмов его в принципе не бывает

Критерий остановки — массив отсортирован, не?

А>что, однако, совcем не мешает оценивать трудоемкость

У этого алогритма нет оценки трудоёмкости в худшем случае.

А>зато замечательно ставит студиозусов в тупик.

Проверка отсортированнасти массива — O(n); вероятность того, что массив отсортирован — 1/n!. Средняя сложность — O(n*n!).

Здравствуйте, Don Reba, Вы писали:


DR>Проверка отсортированнасти массива — O(n); вероятность того, что массив отсортирован — 1/n!. Средняя сложность — O(n*n!).
Да ладно, через O(n^4) должен останавливаться в среднем.

Здравствуйте, denisko, Вы писали:

D>Здравствуйте, Don Reba, Вы писали:


DR>>Проверка отсортированнасти массива — O(n); вероятность того, что массив отсортирован — 1/n!. Средняя сложность — O(n*n!).
D>Да ладно, через O(n^4) должен останавливаться в среднем.

Думаю, даже O(n^2 * log(n)).

Если степень отсортированности массива — число перестановок, которые могут быть сделаны, то:
0 — массив отсортирован
n(n-1)/2 — массив обратно отсортирован

Если степень отсортированности = k, то вероятность, что очередной шаг "попадёт" в перестановку = 2k / (n(n-1)). Мат ожидание числа шагов, чтобы уменьшить степень отсортированности равна n(n-1)/(2k)

Тогда получаем оценку (если каждое попадание уменьшает степень отсортированности на 1):

n(n-1)/2 ( 1/1 + 1/2 + ... + 1/k + ... + 1/ (n(n-1)/2) ) = n(n-1)/2 * log(n(n-1)/2)) = O(n^2 log(n))

Здравствуйте, Константин, Вы писали:

К>Здравствуйте, denisko, Вы писали:

D>>Здравствуйте, Don Reba, Вы писали:


DR>>>Проверка отсортированнасти массива — O(n); вероятность того, что массив отсортирован — 1/n!. Средняя сложность — O(n*n!).
D>>Да ладно, через O(n^4) должен останавливаться в среднем.

К>Думаю, даже O(n^2 * log(n)).
Добавь еще то, что на каждом цикле придется проверять, отсортирован ли массив тогда получится O(n^3 logN), что звучит очень разумно.

Здравствуйте, denisko, Вы писали:

DR>>>>Проверка отсортированнасти массива — O(n); вероятность того, что массив отсортирован — 1/n!. Средняя сложность — O(n*n!).
D>>>Да ладно, через O(n^4) должен останавливаться в среднем.

К>>Думаю, даже O(n^2 * log(n)).
D>Добавь еще то, что на каждом цикле придется проверять, отсортирован ли массив тогда получится O(n^3 logN), что звучит очень разумно.

Можно проверять, например, каждую n-ную итерацию. Тогда асимптотика останется — правда константа вырастет.

Здравствуйте, Константин, Вы писали:

К>Можно проверять, например, каждую n-ную итерацию. Тогда асимптотика останется — правда константа вырастет.
Разумно, тогда у меня из чисто статистических соображений получается N^3 у тебя из перестановочных N^2*logN, скорее всего ты более прав.

Здравствуйте, Аноним, Вы писали:

К>>Первично — понять алгоритм (хотя бы основную идею), тогда и сказать сложность не проблема.
А>Да ладно, вот есть random sort. Идея тривиальна: на каждом шаге мы сравниваем два случайных элемента и при необходимости меняем их местами. Скажи, пожалуйста, какая у него трудоемкость?
Если подойти серьёзно, то следует взглянуть на свойства того, что называется алгоритмом (собственно то, для чего считается алгоритмическая сложность). А конкретно твой random sort не обладает свойством детерминированности. По той же ссылке написано, что делать со случайными данными: "Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.". И сложность тогда считается тривиально.

А>А ведь это тривиальный алгоритм, а если взять что-нибудь типа обхода дерева по алгоритму пьяной макаки или поиск пути по B* c эвристиками.
Аналогично.

Здравствуйте, Щъмых, Вы писали:

Щ>Очень сложно запоминать время работы различных алгоритмов: O(n), O(n^2), O(n*log_n)... Как их запоминать?

прочти это.
доходчиво, основательно, надежно, на века.

Здравствуйте, elmal, Вы писали:

А>>Целенаправленно можно готовиться только к тупым задачкам типа сортировки люков или разворота списков, в нормальных же конторах задачи берут из практики, из числа тех, на которых обломал зубы не один сотрудник.
E>Ух ты . Оказывается есть конторы, которые богосорт используют на практике, не знал . А относительно практики — это меня умиляет. Берется задача, над которой сам лично провозился больше дня, и от кандидата ожидается, что он за 15 минут мгновенно найдет в чем подвох .

Тут у вас аналогия неверная. Сотрудник искал багу в реальном проекте в куче кода. А кандидату дали малый кусок кода, воспроизводящего проблему и он точно знает, что она там есть,
так как его попросили найти подвох. То есть задача гораздо легче.
Такой подход очень хорош, так как
— дается типовая простая проблема "из жизни"
— в гугле не найдешь, что отсеит натаскавшихся зубрил, о которых вы говорите.

Правда, задачки придется часто обновлять, так как после пары-тройки собеседований они в гугле появляются.

Здравствуйте, oncer, Вы писали:

O>Здравствуйте, Щъмых, Вы писали:

Щ>>Очень сложно запоминать время работы различных алгоритмов: O(n), O(n^2), O(n*log_n)... Как их запоминать?

O>прочти это.
O>доходчиво, основательно, надежно, на века.

Да, мне советовали. Есть еще на Java. Она не лучше, разве?

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Константин, Вы писали:

К>>Первично — понять алгоритм (хотя бы основную идею), тогда и сказать сложность не проблема.

А>Да ладно, вот есть random sort. Идея тривиальна: на каждом шаге мы сравниваем два случайных элемента и при необходимости меняем их местами. Скажи, пожалуйста, какая у него трудоемкость?

А>А ведь это тривиальный алгоритм, а если взять что-нибудь типа обхода дерева по алгоритму пьяной макаки или поиск пути по B* c эвристиками.

Я что-то упускаю или это правда тривиально? Разумеется задачу надо "додумать", условие то неполно. Пусть элементарная операция — генерация двух индексов, сравнение и обмен. А условие остановки — массив отсортирован. Вероятность совершить последний обмен в массиве длины k: 1/k * 1/k = 1 / (k^2). Т.е. в среднем понадобится O(k^2) операций. Затем рассмотрим отсортированный массив длины N как последовательность отсортированных массивов длины k.
Проинтегрируем по k от 0 до N. Получим O(N^3). Какие тут трудности могут быть с этим алгоритмом?