Объясните, пожалуйста, простыми словами об асимптотическом О.

Question

как я понял, например, О (x^2) говорит о том, что какая-то функция, например, x^2 + 5000 не будет большей за x^2. Как видно, на начальных значениях, x^2 + 5000 за x^2. В определении есть уточнения по этому поводу? Можете, пожалуйста, просто объяснить доступными словами определение О? Спасибо.

Answer 1

Это означает, что при больших значениях x функция превращается в x^2.
Поскольку у вас функция x^2 + 5000, то большим значением можно считать x=1000 (например) , т. е. тогда когда членом 5000 можно пренебречь, поскольку он мал.
Что считать малым? Установите себе какую нибудь границу, например 5-10%. Когда значение вычисленное по точной формулы отличается от от оценки O (x^2) , тогда говорят достигнуто асимптотическое значение.

Answer 2

Суть в скорости роста количества операций в зависимости от длины входного значения, а 5000 можно убрать так как эта цыфра не зависит от x и сойдёт за 1 операцию.