Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 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.58 MB
Время: 0.049 c
1-5613
Андрей Овдей
2003-02-20 09:19
2003.03.03
Испектор не видит свойства в потомках TForm


1-5510
Fast
2003-02-19 14:36
2003.03.03
Допись данных в начало файла


3-5438
Xjedy
2003-02-13 12:07
2003.03.03
Использование CommandText в ClientDataSet


1-5629
Кирилл
2003-02-20 11:58
2003.03.03
как работать с ShowMessage ?


14-5823
vell
2003-02-13 12:59
2003.03.03
Подскажите пожалуйста компоненты для





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский