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

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

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

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

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

Щ>Очень сложно запоминать время работы различных алгоритмов: O(n), O(n^2), O(n*log_n)... Как их запоминать?
Да это вроде интуитивно все типа
Один цикл по всем элементам — O(N)
Есть вложенный цикл уровня M O(N^M)
Можно разбить на два равных множества и сделать так, что результат есть функция от результатов на этим подмножествах — O(NlogN)
Можешь найти элемент не проходясь по всем элементам коллекции (но проходя не менее чем по 1) — скорее всего O(logN), хотя есть варианты
Что-то сделал с элементов и никто об этом не узнал O(1)
Для более сложных вещей можно попробовать вывести через рекуррентную формулу (вроде Кормен распространялся на эту тему довольно обильно)

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

Pzz>>А не надо запоминать. Надо понимать, откуда это O берется.

Щ>Ого-го

И-го-го.

А в чем практический смысл запонимать информацию, смысл которой вы не понимаете?

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

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

Для экзамена зазубрить, как любые бесполезные факты вроде дат правления царей или правил дифференцирования. В реальной жизни алгоритмы не пишутся с нуля, а реализуются после серьезного ресерча который обязательно включает обращение к первоисточникам. Без такого ресерча может легко статься что логарифмический алгоритм конкретно в ваших условиях ВНЕЗАПНО становится экспоненциальным.

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

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

Заведи блокнотик и записывай.

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

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

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

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

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

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

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

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

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

KK>Заведи блокнотик и записывай.
Куда завести?

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

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

Щ>>Очень сложно запоминать время работы различных алгоритмов: O(n), O(n^2), O(n*log_n)... Как их запоминать?
D>Да это вроде интуитивно все типа
D>Один цикл по всем элементам — O(N)
D>Есть вложенный цикл уровня M O(N^M)
D>Можно разбить на два равных множества и сделать так, что результат есть функция от результатов на этим подмножествах — O(NlogN)
D>Можешь найти элемент не проходясь по всем элементам коллекции (но проходя не менее чем по 1) — скорее всего O(logN), хотя есть варианты
D>Что-то сделал с элементов и никто об этом не узнал O(1)
D>Для более сложных вещей можно попробовать вывести через рекуррентную формулу (вроде Кормен распространялся на эту тему довольно обильно)

То, что надо

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

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

А не надо запоминать. Надо понимать, откуда это O берется.

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

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

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

Pzz>А не надо запоминать. Надо понимать, откуда это O берется.

Ого-го

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

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

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

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

Pzz>А в чем практический смысл запонимать информацию, смысл которой вы не понимаете?
Как это зачем ? Чтоб собеседования лучше проходить . Ведь мало кого волнует что ты умеешь — гораздо важнее то, что ты помнишь . Вот топикстартер заучит алгоритмы, и будет тыщ на 150 претендовать . И ведь пройдет если заучит .

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

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

KK>>Заведи блокнотик и записывай.
Щ>Куда завести?
В карман.

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

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

Pzz>>>А не надо запоминать. Надо понимать, откуда это O берется.

Щ>>Ого-го

Pzz>И-го-го.

Pzz>А в чем практический смысл запонимать информацию, смысл которой вы не понимаете?

Ни в чем. Я не спорю.

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

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

Pzz>>А в чем практический смысл запонимать информацию, смысл которой вы не понимаете?
E>Как это зачем ? Чтоб собеседования лучше проходить . Ведь мало кого волнует что ты умеешь — гораздо важнее то, что ты помнишь . Вот топикстартер заучит алгоритмы, и будет тыщ на 150 претендовать . И ведь пройдет если заучит .
Всё правильно сказал. Зазубрить Кормена и Стандарт, и получать 150 в месяц.

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

E>Как это зачем ? Чтоб собеседования лучше проходить . Ведь мало кого волнует что ты умеешь — гораздо важнее то, что ты помнишь . Вот топикстартер заучит алгоритмы, и будет тыщ на 150 претендовать . И ведь пройдет если заучит .

На выход разве что пройдет. Чтобы претендовать мало заучить константы, надо еще уметь задачки решать.

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

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

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

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

Вообще-то сойдется на бесконечности, это элементарно доказывается. А вот критерия остановки нет потому что у бесконечных итеративных алгоритмов его в принципе не бывает, что, однако, сов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). Какие тут трудности могут быть с этим алгоритмом?