Вопрос о коэффициенте масштабирования Big O

Question

У меня есть 2 алгоритма, чтобы что-то сделать (например, поиск по списку), один имеет линейную сложность, а другой - сложность журнала (O (log n). Если я сравниваю операцию на 100 и 1000 единиц, могу ли я сказать, что линейный алгоритмимеет коэффициент масштабирования x10?

Как выразить коэффициент масштабирования лог-алгоритма? Например, 100 элементов занимает 2 секунды, 1000 элементов занимает 3 секунды. Журнал 1000 равен 3, журнал 100 равен 2. Так чтоэто коэффициент масштабирования? x1,5?

Я вижу, что рост во времени является логарифмическим. Или вы просто говорите, что коэффициент масштабирования является логарифмическим? Но что бы вы рассчитали, если бы в примере сравнивалось от 100 до 1000 элементов?

Answer 1

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

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

Answer 2

Я бы сказал, что «оно масштабируется линейным / квадратичным / кубическим / логарифмическим / экспоненциальным образом», я бы не стал ссылаться на точный коэффициент масштабирования вообще. Большой O не о конкретных временах, это способ поместить алгоритмы в определенные классы, т.е. линейный класс, логарифмический класс и т. д.

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

Answer 3

Как правило, вы не можете вычислить числовой коэффициент масштабирования только из сложности Big O, поскольку сложность Big O не включает коэффициенты и константы, которые имеют решающее значение для вычисления коэффициента масштабирования.

Если алгоритм A имеет фактическую сложность (1/1000) * n + 100, а алгоритм B имеет фактическую сложность 100*log(n) + 1, алгоритм A равен O (n), а алгоритм B - O (log (n)). Однако, когда вы переходите от n от 100 к n от 1000, A переходит от стоимости от 100,1 до 101, а B - от 201 до 301. Фактическое время работы алгоритма A увеличивается только на 1%, в то время как фактическое время работы алгоритма B увеличился на 50%.

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