BigO Нотация, понимание

Question

Я видел в одном из видео (https://www.youtube.com/watch?v=A03oI0znAoc&t=470s), что, если предположить, что f (n) = 2n +3, то BigO - это O (n).

Теперь мой вопрос:Я разработчик, и мне дали O (n) как верхнюю границу f (n), тогда как я пойму, какое именно значение является верхней границей, потому что в 2n +3 мы удаляем 2 (так как это константа) и 3 (потому что это тоже константа). Итак, если моя функция f (n), где n = 1, я не могу сказать, что g (n) имеет верхнюю границу, где n = 1.

1не может быть верхним пределом для 1. Мне трудно это понять.

Answer 1

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

Итак, нотация big-O поможет вам лучше классифицировать проблему, а затем попытаться решить ее с помощью алгоритма, сложность которого такая же, как у big-O. Если вам повезло найти 2 или более алгоритмов с такой сложностью, то вам нужно будет обдумать их, используя другой критерий.

Answer 2

Я знаю, что это частичный (и, вероятно, неправильный ответ)

Из Википедия ,

Обозначение Big O характеризует функции в соответствии с темпами их роста: различные функции с одинаковой скоростью роста могут быть представлены с использованием одинаковых обозначений O .

В вашем примере f (n) = 2n + 3 имеет такую ​​же скорость роста, как f (n) = n

Если вы нанесете на график функции, вы увидите, что обе функции имеют одинаковый линейный рост; и при n -> бесконечность разница между 2 становится минимальной.

В обозначениях Big O f (n) = 2n + 3, когда n = 1 ничего не значит; вам нужно смотреть на тренд, а не на сдержанные значения.