пары соседей, претендующих
пары соседей, претендующих на первую парту в классе. Тогда алгоритм оценивался как квадратичный относительно числа учеников, и это нас не слишком беспокоило.
Несколько изменив условие, будем рассматривать всевозможные способы рассадки всех n учеников на n местах. Легко заметить, что таких способов существует ровно
n?(n-1)?(n-2)?...?2?1 = n!
Уже в маленьком классе, с десятью учениками, количество вариантов превосходит 3.5 млн. Предположим, наш компьютер столь хорош, что справится с такой порцией за одну секунду. Но стоит посадить в класс еще 5 учеников, и времени потребуется уже в 11?12?13?14?15=360360 раз больше, или более 4 суток непрерывного счета.
Как видим, применять алгоритмы с вычислительной трудоемкостью O(n!) надо очень осторожно, если хотим дождаться конечного результата. Что же делать?
Заметим, для справки, что ускорить перебор в приведенном примере невозможно, разве что изменить постановку задачи. В нашем случае, скажем, более конкретная постановка задачи, включающая
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
