порядка",
порядка", как-то: O(n2) и O(n3). В общем случае, если эффективность алгоритма определяется вычислительной сложностью обработки многочлена порядка k, часто удовлетворяются оценкой O(nk), не обращая внимания, согласно свойству (b), на старший коэффициент.
Такой подход, как правило, оправдывает себя для "больших" n. Действительно, как следует из определения O-асимптотики, - и это демонстрируют приводимые графики, - сколь бы ни был мал коэффициент при старшем k-члене и, напротив, велик - при любом другом m-члене (m<k), вклад первого из них в поведение всего многочлена рано или поздно становится решающим.
Однако нередко представляет интерес более тщательный анализ. В частности, когда сравнивают эффективность двух равноценных, с точки зрения O-асимптотики, алгоритмов. Тогда возникает необходимость в уточнении первого "приближения".
Так, оценка O(n3) в последнем примере получена нами без раскрытия скобок в произведении. Для ее уточнения достаточно проделать
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
