Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Оценка алгоритмов

Петька © (2008-01-08 23:54:00)
Уважаемые мастера может кто поможет.
Преподаватель сказал сделать по каждому из O(n) O(n2) O(log2n)
алгоритм как пример оценки алгоритма.

Я не понял что от меня хотят, как минимум хотя бы разъясните.
Не в понятках я.:(

Vendict (2008-01-09 23:30:00) [1]
что-то я кроме двоичного поиска ничего не вспоминаю...
ведь O(log2n) получается только при делении пополам.
можешь конечно предоставить ему как пример процедуру добавления нового элемента в двоичное дерево. тоже O(log2n) но боюсь не только ты, но и он не поймёт, о чём речь )

придётся лезть за своим блокнотом...

только это "псевдокод". a- массив (куча)

procedure heapify (i) l:=2*i; r:=2*i+1; if l<=heapsize(a) and a[l]>a[i] then large:=l else large:=i; if r<=heapsize(a) and a[r]>a[large] then large:=r; if large<>i then { swap(a[i],a[large]) heapify(large) } end

palva (2008-01-09 20:58:00) [2]
> сказал другое что нить показать
Тогда пусть сюда приходит. Мы ему покажем.

Петька (2008-01-09 20:30:00) [3]
1) O(n)
for i:=0 to n do
c := Power((a * b),n);

2) O(n^2)
for i:=0 to n do
For j:=0 to n do
c := a*b*n;

тема с двоичным поиском ему не понравилась, сказал другое что нить показать

Петька (2008-01-09 16:00:00) [4]
понял, спасибо за ответы!!!
но все равно надо будет потом почитать на эту тему чтонить,убрать пробел так сказать

Vendict (2008-01-09 12:30:00) [5]
c := a * b; --- O(n) ---- O(1) одна операция for i:=0 to n do c := Power((a * b),n); --- O(n2) цикл, следовательно O(n) for i:=0 to n do For j:=0 to n do --- O(n^2)

классический пример O(log2n) - это двоичный поиск.

MBo (2008-01-09 05:32:00) [6]
>Я правильно понял?
нет. лучше несложные книжки по алгоритмам почитать

Петька (2008-01-09 01:25:00) [7]
спасибо.
Я правильно понял?

c := a * b; --- O(n)

for i:=0 to n do
c := Power((a * b), n); --- O(n2)

Vendict (2008-01-09 00:08:00) [8]
вот этого должно хватить, чтобы понять.
там даже с примерами алгоритмов.

http://algolist.manual.ru/misc/o_n.php

palva (2008-01-09 00:04:00) [9]
Это значит если объем входных данных увеличивается в два раза, то объем вычислений увеличивается примерно:
в два раза (линейный поиск в массиве)
в четыре раза (сортировка массива простейшими методами)
на какую-то постоянную величину (дихотомический поиск)

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »