Сложность. Почему константы не имеют значения?

Question

Может кто-нибудь объяснить мне простым способом, почему константы не имеют значения, когда дело доходит до больших О-нотаций? Почему сложность остается такой же, когда вы добавляете константу. Это не домашнее задание, я просто хочу лучше это понять. Позвольте мне получить эту прямую большую O, чтобы увидеть поведение функции, когда она приближается к бесконечности, верно?

Я понял. Большое спасибо всем.

Answer 1

Это не имеет значения для теории сложности, которая заинтересована только в том, как функция масштабируется при увеличении размера ввода.

Константа не влияет на поведение функции в качестве размеров вводавообще стремиться к бесконечности.

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

Разница между теорией сложности и практикой.

Answer 2

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

Таким образом, мы говорим, что константа «не имеет значения», потому что она никогда не может изменить асимптотические отношения между кривыми.

Answer 3

Ответ ... по определению.Если какая-то функция f(x) имеет значение big-O какой-либо функции g(x), это просто означает, что f(x) "в конечном итоге" меньше, чем некоторое постоянное время g(x).(т.е. для достаточно больших x).Фактическое значение константы не имеет значения;и положение «в конечном итоге» поведения - при условии, что оно верно для достаточно большой x и достаточно большой константы, вы покрыты.

Вы можете добавить константы или что-нибудь еще сменьше O, и это не имеет значения - все дело в том, какой термин растет быстрее, а какой доминирует при росте x.

Answer 4

Константы не важны в нотации big-O, потому что проблема в масштабируемости

Answer 5

Big O объясняет, как изменяется сложность при увеличении входных данных. Чем больше ваш вклад, тем менее важными являются константы. Например, умножение чего-либо на 10 значительно менее важно, чем возведение в квадрат чего-либо, когда n достигает одного миллиона или одного миллиарда. Большое О не является точным измерением, это способ поместить ваш алгоритм в грубый класс сложности, чтобы вы могли округлить константы, потому что они не имеют смысла с огромными значениями n.

Answer 6

Нотация Big-O о том, как использование ресурсов (время, память) изменяется при изменении количества элементов. Так, например, если мой компьютер может сортировать 10 элементов за 1 секунду, 20 элементов за 4 секунды и 30 элементов за 9 секунд, то это O (n & sup2;).

Если я могу отсортировать те же самые вещи вручную за 10 секунд, 40 секунд и 90 секунд, соответственно, тогда я все равно буду O (n & sup2;), но мой постоянный коэффициент будет в 10 раз больше: проблема такого же размера требует мне в десять раз длиннее компьютера.