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

21 Авг 2019 в 06:13
181 +1
0
Ответы
1

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

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

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

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

20 Апр 2024 в 13:21
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир