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

AS>>А причем тут предел ?
AS>>Можно график начертить, и увидеть, что квадратичная фунция растет быстрее линейной, и при n стремящимся в бесконечность, значение C можно принять за 1, т.к. это константа, т.е. она не зависит от n

SaZ>Рисовал график. От меня требовали именно теоретическое обоснование.

Наверное аналитическое обоснование. Ту же производную можно обосновать геометрически, а можно аналитически, чисто через формулы.
Ну если хотели аналитическое обоснование, то тут тоже довольно просто:
1. O(С*n) < O(n^2)
2. O(С*n) / O(n^2) < 1
3. С/n < 1 для всех C < n
4. lim C/n -> 0 при n -> oo

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

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

S>>>и поиск цикла в list

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

AS>какой специальный подход ? два указателя "быстрый" и "медленный", догнал быстрый указатель медленный значит есть циклы.

AS>проще через хэш-таблицу решить, но обычно говорят, что нельзя её использовать.

Если в задаче есть требование найти узел где начинается цикл то задача выглядит гораздо более интереснее.

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

H>Число элементов списка известно заранее?

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

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

aik>пост же не про задачи сами по себе, а что одну и ту же пластинку ставят раз за разом. такое ощущение что это какие то hunger games заочные, ищут самого выносливого и/или мотиварованного что ли.

Это палка о двух концах. С одной стороны почти у всех компаний процесс собеседования отдаёт дибилизмом так или иначе. Исключений здесь нет по той лишь причине, что не существует критерия успешного найма. С другой стороны, взрослые люди понимают, что если они идут выполнять работу за деньги, то это право того, кто платит, решать, каким образом собеседовать. Поэтому новоиспечённые вайтишники приняли статью тепло, ведь там об их общей боле написано, а людям с опытом нытьё не поняли от слова совсем.

Что скрывать, я и сам лет 5-7 был Д'Артаньяном и имел на всё своё мнение, но опыт (в том числе и найма людей) научил соблюдать субординацию и относиться с пониманием к тому, что кажется странным на первый взгляд.

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

M>Это всё скорее всего "отсчитывается" библиотеками, которые ты подцепил

Да, но можно ведь убить производительность неаккуратной обвязкой. Как у автора статьи — море пафоса и квадратичная сложность на ровном месте. Особо доставляют плюсники конечно, те, кто верует в святаго C++ и шаблоны его, и считает алгоритмы ересью.

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

C>Что скрывать, я и сам лет 5-7 был Д'Артаньяном и имел на всё своё мнение, но опыт (в том числе и найма людей) научил соблюдать субординацию и относиться с пониманием к тому, что кажется странным на первый взгляд.

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

Здравствуйте, Тёмчик, Вы писали:

Тё>Особо доставляют плюсники конечно, те, кто верует в святаго C++ и шаблоны его, и считает алгоритмы ересью.

Не кури это больше!

SaZ>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?
Задача некорректна. Константа должна быть в обоих выражениях. Иначе результат сравнения зависит от ее размера. При С бесконечно большом, условие не выполняется.

Возможно, именно такой ответ и ожидался.
Хотя, смысла в такой задаче на собеседовании я не вижу.

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

Тё>>Особо доставляют плюсники конечно, те, кто верует в святаго C++ и шаблоны его, и считает алгоритмы ересью.
CC>
CC>Не кури это больше!

Вот ты, хотя на шаблоны не мастурбируешь, а веришь в константу минимальную, перекрывающую алгоритмическую сложность.

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


SaZ>>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?
N>Задача некорректна. Константа должна быть в обоих выражениях.
Корректна.

N>Хотя, смысла в такой задаче на собеседовании я не вижу.
Смысл- отсеять таких, кто не видит в bigO смысла.

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


SaZ>>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?
N>Задача некорректна. Константа должна быть в обоих выражениях. Иначе результат сравнения зависит от ее размера. При С бесконечно большом, условие не выполняется.

Константа на то и константа, что ни от чего не зависит.
Как говорится, если бы у бабушки был член с яйцами, она была бы дедушкой.
Так и тут, константа от чего-то зависящая, называлась бы функцией

aik>Ну и какой смысл спрашивать вот этот вот кодинг раз за разом? Он же точно не будет целыми днями только этим и заниматься
Поэтому нужно спрашивать архитектуру высоконагруженного приложения! Ведь программисты точно целыми днями только этим и занимаются. По 3 высоконагруженных приложения в час выпекают в среднем.

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

SaZ>>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?
N>Задача некорректна. Константа должна быть в обоих выражениях. Иначе результат сравнения зависит от ее размера. При С бесконечно большом, условие не выполняется.

C — константа, n — переменная. Какую бы огромную С ты заранее ни взял, всегда можно найти такое n, где C*n < n*n. Собственно при n = С+1 оно уже так.


Некорректность тут разве что только в том, что человек сразу сказал что в универе это не проходил, понимает так, как понимает и 45 минут про это мучать просто бессмысленно. Или приняли бы его объяснения "на пальцах" или уж засчитали минус да успокоились.

Здравствуйте, Тёмчик, Вы писали:

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

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

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

SaZ>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?

1) Графически: рисуем графики функций y = Cx и y = x^2, показываем что первый растёт медленнее.
2) Вычитаем функции друг из друга и получаем y = x^2 — Cx, показываем что на правой полуплоскости это возрастающая функция (если уж очень прикопались, через взятие производной y = 2x)

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

SaZ>>Рисовал график. От меня требовали именно теоретическое обоснование.

AS>Наверное аналитическое обоснование. Ту же производную можно обосновать геометрически, а можно аналитически, чисто через формулы.
AS>Ну если хотели аналитическое обоснование, то тут тоже довольно просто:
AS>1. O(С*n) < O(n^2)
AS>2. O(С*n) / O(n^2) < 1
AS>3. С/n < 1 для всех C < n
AS>4. lim C/n -> 0 при n -> oo

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

По факту меня не взяли, но я и не расстроился. Сейчас всё хорошо и в профессиональном и в карьерном плане.

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

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

SaZ>>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?

MD>1) Графически: рисуем графики функций y = Cx и y = x^2, показываем что первый растёт медленнее.
MD>2) Вычитаем функции друг из друга и получаем y = x^2 — Cx, показываем что на правой полуплоскости это возрастающая функция (если уж очень прикопались, через взятие производной y = 2x)

y = 2x — C

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

AS>Ну если хотели аналитическое обоснование, то тут тоже довольно просто:
AS>1. O(С*n) < O(n^2)
AS>2. O(С*n) / O(n^2) < 1
AS>3. С/n < 1 для всех C < n
AS>4. lim C/n -> 0 при n -> oo

Мне в своё время приходилсь вытравливать из себя математика, когда ударился в разработку софта. Вот так вот, обрах мышления, который способстовал решению задач из матанализа, сильно мешал писать программный код. Это не только у меня так, судя по тому, какие отзывы о том коде, который пишут математики. Но и образ мышления прогера-практика достаточно далёк от образа мышления математика-теоретика. Выше задачка для математика, а не для разработчика программного кода.

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

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


S>Мне в своё время приходилсь вытравливать из себя математика, когда ударился в разработку софта. Вот так вот, обрах мышления, который способстовал решению задач из матанализа, сильно мешал писать программный код. Это не только у меня так, судя по тому, какие отзывы о том коде, который пишут математики. Но и образ мышления прогера-практика достаточно далёк от образа мышления математика-теоретика. Выше задачка для математика, а не для разработчика программного кода.

Зачем вытравливать, математика полезна, и математический склад ума вполне пригождается в софтописании.

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

AS>Зачем вытравливать, математика полезна, и математический склад ума вполне пригождается в софтописании.

Да вот нифига. С 10-ти лет решал задачки по математике, любил это дело, особенно матанализ. Но когда стал пытаться писать код, то стало понятно, что думать нужно по-другому. При написании кода режим мышления должен быть другим, больше писательским, чем математическим. Иначе код получается похожим на математические выкладки.