Оценка сложности процедуры

← →
michael_b (2003-02-14 17:15) [0]

Как оценить сложность такой процедуры:
procedure A;
var
i, n,k: Integer;
begin
for i:=1 to N do
begin
k:=4;
repeat
k:=k*sqrt(k*1.5)*k
until k>n
end;

← →
Cr@sh © (2003-02-14 17:18) [1]

не понял... а где присваивается значение переменной n????

← →
han_malign © (2003-02-14 17:25) [2]

3 - по количеству строк эфективного кода...
2 Cr@sh © (14.02.03 17:18)
- ну..., в принципе... - n<2147483648 :)))

← →
michael_b (2003-02-14 17:34) [3]

> не понял... а где присваивается значение переменной n????

В том-то и дело в задании звучит в зависимости от исходных данных

← →
Anatoly Podgoretsky © (2003-02-14 17:50) [4]

11 строк

← →
Manulo © (2003-02-14 18:04) [5]

Супер тяжёлая...
> не понял... а где присваивается значение переменной n????

n - это наверное глобальная переменная или константа

← →
DAC © (2003-02-14 18:10) [6]

Сложность алгоритма оценить невозможно - нарушен баланс begin-end, а так о(n^2) (при наличии end).

← →
michael_b (2003-02-14 18:32) [7]

> Сложность алгоритма оценить невозможно - нарушен баланс
> begin-end, а так о(n^2) (при наличии end).

Извиняюсь забыл end;

← →
michael_b (2003-02-14 18:39) [8]

← →
michael_b (2003-02-14 18:41) [9]

> о(n^2)

Поясните

← →
Сергей (2003-02-14 19:19) [10]

квадратичная зависимость времени выполнения от N. Точнее пропорциональная квадратичной.

> Сергей (14.02.03 19:19)

не совсем
точнее так: существует константа C, такая что
для любого наперед заданного N время выполнения (кол-во шагов) < C*(N^2)
или так: при N -> к бесконечности lim(время выполнения (кол-во шагов))/(N^2) = const.
:-))

Вообще, интереснейшая тема - универсальная оценка сложности любых объектов. Методика и единицы измерения. Кто что думает об этом ? Я считаю, что давно пора было разработать... :)

Возможно, отталкиваясь от количества состояний, которые способен принимать данный объект ...

← →
Asker (2003-02-14 23:24) [13]

рекомендую книжки по алгоритмам (Ахо, Хопкрофт "Структуры данных и алгоритмы" и др.)

Оценка сложности процедуры Найти похожие ветки