Как предварительно вычисляется обработка с помощью обозначения сложности?

Question

Предположим, у меня есть алгоритм, который работает в O (n) для каждого ввода размера n, но только после этапа предварительного вычисления O (n^2) для данного размера n. Рассматривается ли алгоритм O (n) еще с амортизацией O (n^2)? Или большой O учитывает только один «запуск» алгоритма при размере n, и поэтому шаг предварительной вычисления включается в нотацию, делая истинную нотацию O (n + n^2) или O (n^2)?

Answer 1

Это не редкость, потому что это объясняется тем, что они явно разделяют затраты на две разные части. Например, в range minimum query problem обычно говорят о том, что люди говорят о вещах вроде & langle; O (n), O (1) & rangle; -time решение проблемы, где O (n) обозначает стоимость предварительной обработки и O (1) обозначает стоимость поиска. Вы также видите это со строковыми алгоритмами: suffix tree provides an O(m)-preprocessing-time, O(n+z)-query-time solution to string searching, а Aho-Corasick string matching offers an O(n)-preprocessing-time, O(m+z)-query-time solution.

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

Answer 2

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

Таким образом, если получение в результате R требует, чтобы выполнить шаги A и B, а затем complexity(R) = complexity(A) + complexity(B). В вашем конкретном примере это будет O(n^2).

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

Однако анализ сложности и B будет обычно выполняться изолированно, если они не пересекаются.

Таким образом, это количество времени, затрачиваемого на получение результатов, но вы можете (и обычно) рассуждать об отдельных шагах независимо друг от друга.

---

Бывают случаи, когда вы можете указать не только самую медленную часть трубопровода. Простым примером является BFS со сложностью O(V + E). С E = O(V^2) может возникнуть соблазн написать сложность BFS как O(E) (с E > V). Однако, это было бы некорректно, так как может быть график без краев! В этих случаях вам все равно придется перебирать все вершины.

Answer 3

Точка записи O (...) не должна измерять, насколько быстро работает алгоритм, поскольку во многих конкретных случаях O (n) может быть значительно медленнее, чем, например, O (n^3). (Представьте алгоритм, который выполняется в 10^100 n шагов по сравнению с тем, который выполняется с шагом n^3/2.) Если я скажу вам, что мой алгоритм работает в O (n^2), он ничего не говорит о том, как долгое время потребуется для n = 1000.

Точка O (...) должна указывать, как работает алгоритм при увеличении размера ввода. Если я скажу вам, что мой алгоритм работает в O (n^2) времени, и для n = 500 требуется 1 секунда, тогда вы ожидаете скорее 4 секунды для n = 1000, а не 1,5, а не 40.

Итак, чтобы ответить на ваш вопрос - нет, алгоритм не будет O (n), это будет O (n^2), потому что, если я удвою размер ввода, время будет умножено на 4, а не на 2.