Большой-O: Как Вы знаете что алгоритм дать для определенной временной сложности?

Вы правы, вы должны знать временные сложности для различных алгоритмов, чтобы знать это. Вы должны знать временные сложности для сортировки, поиска элементов в словаре, в хэш-таблице, поиска объединения, потоковых графов, DFS, BFS, минимальных остовных деревьев и т. Д. Это основы.

Введение в алгоритмы должно вас хорошо освоить.

1. Подумайте как следует.
2. Придумайте алгоритм для задачи
3. Проанализируйте его, чтобы определить временную сложность (большой О).
4. Если временная сложность - это то, что вас просили произвести, то все готово.
5. Else goto 1.

Если серьезно, вам необходимо знать сложность алгоритмов для решения распространенных проблем, таких как итерация, поиск, сортировка, поиск по хеш-таблице и т. Д. Например, это очень полезно для знайте, что простой алгоритм сортировки, такой как пузырьковая сортировка, равен O (n ^ 2), а быстрая сортировка - O (n log n) в среднем случае. Также важно уметь быстро анализировать алгоритм, чтобы определить его сложность и увидеть, как его можно изменить, чтобы сделать его быстрее.

Это не так уж далеко от истины. Есть пара систематических методов, но это тяжелая работа, и даже тогда они имеют тенденцию "сокращаться" в какой-то момент.

Big-O дает верхнюю границу. Если кто-то спросит вас о каком-либо алгоритме, а вы не знаете, вы можете сказать O(n^n) и, вероятно, будете правы (хотя существуют еще более медленные алгоритмы). Конечно, это не жесткая граница.

По сути, "короткий путь" - это точка вдохновения, когда вы замечаете закономерность, доказывающую определенную верхнюю границу.

99% времени большинство людей просто используют свою интуицию, чтобы найти хороший способ взглянуть на алгоритм, а затем сделать достаточно, чтобы доказать эту границу. Например, вместо того, чтобы смотреть на фактический поток выполнения, принято говорить "каждый элемент обрабатывается не более x раз, каждый раз занимая постоянное время" (для алгоритма O(n)). Вы возможно упустили тот факт, что, например, обрабатывается не более log n элементов, но если вы действительно понимаете, что делает алгоритм, это достаточно маловероятно.

Конечно, это, вероятно, не поможет вам пройти курс алгоритмов.

Что касается систематических методов - ну, есть видеокурс "MIT 6.046J / 18.410J Introduction to Algorithms", который можно посмотреть на YouTube. Лектор - один из авторов очень уважаемого учебника по алгоритмам.

Это может быть более академично, чем то, что вы ищете, но стоит знать, что для определенных проблем можно доказать, что любой алгоритм, который их решает, не будет работать лучше чем некоторая нижняя граница. Например, сортировка сравнения не сработает лучше, чем O (n log n) . Другой пример - Башни Ханоя, любое решение которых должно быть экспоненциальным из-за способа построения проблемы.

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

В любом случае, иногда правильный вопрос, который нужно задать: можно ли это сделать в заданное время?

Кроме того, как все сказали: иметь практическое знание того, какие алгоритмы используются для решения каких проблем. У Боба есть хорошие примеры. (Просто обратите внимание, что операции с хеш-таблицами не всегда гарантируют O (1), но ожидаются.)

Я делаю это немного более прагматично.

1. Получите алгоритм. Вы либо уже знаете алгоритм, либо найдете его в Интернете, либо создадите его сами.
2. Подражайте алгоритму в уме.
3. Увеличьте размер вашего набора (n) на миллиард
4. Снова подражайте ему в уме, время увеличится на миллиард? тогда это O (n), увеличилось ли оно на gazillion * log gazillion, тогда это O (n log n)

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