* O(O(f(n)))=O(f(n))
*
O(O(f(n)))=O(f(n))
*
O(f(n))?O(g(n))=O(f(n)?g(n))
Кроме введенной терминологии, полезна и другая, т.н. o-нотация ("о-малое"). Обозначение o(f(n)) относится к функциям, которые растут быстрее f(n).
Вновь обращаясь к примеру с суммой арифметической прогрессии, можем сказать, что асимптотическая эффективность алгоритма непосредственного суммирования n элементов соответствует линейной сложности, поскольку его быстродействие, то есть число шагов, согласно свойству (a), есть O(n).
Вообще говоря, если алгоритм связан с обработкой n входных элементов, и аналитического выражения - формулы - для быстрого вычисления результата в нашем распоряжении нет, то достижение лучшей эффективности, чем O(n), если это вообще возможно, следует рассматривать как большой успех.
А вот более трудоемкие алгоритмы, при том же объеме входного набора, существуют, и ускорить процесс далеко не всегда удается.
Пример #3.
Независимый выбор пары соседей для первой парты в классе из
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
