Как расчитать порядок роста алгоритма? Допустим дано два алгоритма: Метод золотого сечения и Метод деления пополам, как найти их порядок роста (по кол-ву шагов)?

Предыдущий
вопрос Следующий
вопрос

Для определения порядка роста алгоритма необходимо оценить количество шагов, которые каждый из них совершает для решения задачи определенной сложности.

Метод золотого сечения
Метод золотого сечения ищет оптимальное значение функции на отрезке, уменьшая его в определенной пропорции на каждом шаге. Для определения порядка роста этого алгоритма можно выразить количество шагов в зависимости от длины текущего отрезка. Например, если на каждом шаге отрезок делится на два и отбрасывается одна из его частей, то порядок роста метода будет O(log n), где n - длина отрезка.

Метод деления пополам
Метод деления пополам также ищет оптимальное значение функции на отрезке, однако отличается от золотого сечения тем, что делит отрезок пополам на каждом шаге. Поэтому количество шагов в этом методе также можно оценить по длине отрезка и определить его порядок роста как O(log n).

Таким образом, для обоих методов порядок роста по количеству шагов будет O(log n), где n - размер задачи.