n учеников можно
n учеников можно осуществить n(n-1) способами.
Если предстоит рассмотреть все варианты для выбора наиболее приемлемого в некотором заданном смысле, то трудоемкость алгоритма, очевидно, оценивается как O(n2), или квадратичная. Согласно (b)-свойству O-операций, собственно константа, определяющая трудоемкость каждого отдельного шага оценки "приемлемости", скрыта внутри обозначения, и даже может быть нам неизвестна.
Пример #4.
Совсем не трудно представить еще менее эффективный алгоритм. Предлагается для набора из n попарно неравных отрезков подсчитать количество всевозможных "троек", из которых получаются невырожденные треугольники.
Здесь, очевидно, предстоит проверить n(n-1)(n-2) вариантов, что соответствует кубической трудоемкости - O(n3).
В наших примерах речь идет о верхних оценках скорости роста трудоемкости. Обычно, при поверхностном анализе алгоритма, такой оценки вполне достаточно, особенно когда речь идет об алгоритмах с трудоемкостью "разного
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
