Форум: "Потрепаться";
Текущий архив: 2003.03.03;
Скачать: [xml.tar.bz2];
Вниз
Оценка сложности процедуры Найти похожие ветки
← →
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]
> Сложность алгоритма оценить невозможно - нарушен баланс
> begin-end, а так о(n^2) (при наличии end).
Извиняюсь забыл end;
← →
michael_b (2003-02-14 18:41) [9]
> о(n^2)
Поясните
← →
Сергей (2003-02-14 19:19) [10]квадратичная зависимость времени выполнения от N. Точнее пропорциональная квадратичной.
← →
DAC (2003-02-14 19:35) [11]
> Сергей (14.02.03 19:19)
не совсем
точнее так: существует константа C, такая что
для любого наперед заданного N время выполнения (кол-во шагов) < C*(N^2)
или так: при N -> к бесконечности lim(время выполнения (кол-во шагов))/(N^2) = const.
:-))
← →
Сергей Чурсин (2003-02-14 21:26) [12]Вообще, интереснейшая тема - универсальная оценка сложности любых объектов. Методика и единицы измерения. Кто что думает об этом ? Я считаю, что давно пора было разработать... :)
Возможно, отталкиваясь от количества состояний, которые способен принимать данный объект ...
← →
Asker (2003-02-14 23:24) [13]рекомендую книжки по алгоритмам (Ахо, Хопкрофт "Структуры данных и алгоритмы" и др.)
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2003.03.03;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.009 c
