Big-O: Откуда ты знаешь, какой алгоритм дать для определенного времени сложности?

Question

Итак, когда кто-то просит вас дать алгоритм O (n) или O (nlogn) для вычисления чего-либо, как вы знаете, что ответить? Похоже, единственный способ ответить на этот вопрос - заранее знать временные сложности различных алгоритмов, а не придумывать что-то на месте. Правильно ли я предположил это?

Answer 1

простые случаи:

Итерация по списку - O (n)

Одиночная двоичная или древовидная операция - O (log n) (что означает, что вставка n элементов в дерево - это n log n)

Операция взлома - O (1)

Полная проблема NP (здесь вам нужен некоторый опыт для развития интуиции) - экспоненциальное время в целом (на практике для многих задач может быть применена эффективная эвристика)

для графа с E ребрами и V вершинами сложность F (E, V) в зависимости от характера алгоритма и плотности графа. E + V для хорошего DFS / BFS.

Почти каждый алгоритм может быть разбит на множество вышеупомянутых (или похожих) небольших блоков. Когда блоки объединяются рекурсивно, как A-includes-B, сложность увеличивается, когда блоки следуют друг за другом, как A-then-B, сложность max (сложность A, сложность B)

Answer 2

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

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

Answer 3

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

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

«Ярлык» - это, по сути, точка вдохновения, когда вы обнаруживаете образец, который доказывает некоторую конкретную верхнюю границу.

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

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

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

Answer 4

1. Думайте очень усердно.
2. Придумайте алгоритм задачи
3. Анализируйте его, чтобы определить его сложность по времени (big-O).
4. сложность времени - это то, что вам было предложено произвести, все готово.
5. Иначе Перейти к 1.

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

Answer 5

То, как я это делаю, немного более прагматично.

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

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

Answer 6

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

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

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

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