Как расчитать порядок роста алгоритма?

Question

[RokkerRuslan]

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

Answer 1

[Сергей]

Ваши алгоритмы суть одного и того же. Просто в первом отрезок делится в пропорции золотого сечения, а во втором случае отрезок делится пополам.

У обоих сложность O(log n).

Comments

[Killy]

В одном случае поиск решения f (x) = 0, в другом случае - поиск экспремума, т.е. f ' (x) = 0 по сути. Читайте внимательнее.

(Я сам сначала подумал, что речь об однои и том же, и цель вопроса - найти подтверждение того, что делить золотым сечением быстрее, чем поровну - пусть и в константное число раз.)

[jcmvbkbc]

Я вам больше скажу, любое деление работает за O(log n), основание логарифма только будет разным.

[jcmvbkbc]

@Killy да одно и то же это, разница только в том, на сколько частей делится отрезок на каждом шаге

[myrslok]

Не очень-то и разным. O(log_a n) = O(log_b n).

Answer 2

[Killy]

Если вопрос в том, как именно выводится оценка сложности для произвольного алгоритма, то гуглить про Вычислительную Сложность алгоритмов, Теорию Сложности.
Что-нибудь такое: www.structur.h1.ru/ocenka.htm