Линейная сложность и квадратичная сложность

Question

Я просто не уверен ...

Если у вас есть код, который может быть выполнен в любой из следующих сложностей:

1. Последовательность O (n), как например: два O (n) в последовательности
2. О (п & sup2;)

Предпочтительной версией будет та, которая может быть выполнена за линейное время. Будет ли время, когда последовательность O (n) будет слишком большой, и что O (n & sup2;) будет предпочтительным? Другими словами, всегда ли утверждение C x O (n)

Почему или почему нет? Какие факторы могут повлиять на состояние, чтобы было лучше выбрать сложность O (n & sup2;)?

Answer 1

Я думаю, что здесь есть две проблемы; во-первых, что говорит нотация, во-вторых, что вы на самом деле измеряете в реальных программах

1. большой O определяется как предел как n -> бесконечность, так что в терминах большого O, O (n)

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

Answer 2

Если ваша константа C больше, чем значение n, тогда алгоритм O (n²) будет лучше.

Answer 3

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

Answer 4

C x O (n)

Когда C велико, а n мало, тогда C x O (n)> O (n²). Однако C всегда постоянен, поэтому, когда n масштабируется до большого числа, C x O (n)

Поэтому, когда n большое, O (n) всегда лучше, чем O (n²).