Очень сложно запоминать время работы различных алгоритмов: 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). Точно не ошибешься и ответ будет корректен . А так — запоминать не надо, надо понять почему так.

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

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

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

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

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

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

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

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

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

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

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

Щ>Очень сложно запоминать время работы различных алгоритмов: 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 берется.

Ого-го

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

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 претендовать . И ведь пройдет если заучит .

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

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

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