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

← →
Петька (2008-01-08 23:54) [0]

Уважаемые мастера может кто поможет.
Преподаватель сказал сделать по каждому из O(n) O(n2) O(log2n)
алгоритм как пример оценки алгоритма.

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

← →
palva © (2008-01-09 00:04) [1]

Это значит если объем входных данных увеличивается в два раза, то объем вычислений увеличивается примерно:
в два раза (линейный поиск в массиве)
в четыре раза (сортировка массива простейшими методами)
на какую-то постоянную величину (дихотомический поиск)

← →
Vendict © (2008-01-09 00:08) [2]

вот этого должно хватить, чтобы понять.
там даже с примерами алгоритмов.

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

← →
Петька (2008-01-09 01:25) [3]

спасибо.
Я правильно понял?

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

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

← →
MBo © (2008-01-09 05:32) [4]

>Я правильно понял?
нет. лучше несложные книжки по алгоритмам почитать

← →
Vendict © (2008-01-09 12:30) [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) - это двоичный поиск.

← →
Петька (2008-01-09 16:00) [6]

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

← →
Петька (2008-01-09 20:30) [7]

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;

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

> сказал другое что нить показать
Тогда пусть сюда приходит. Мы ему покажем.

что-то я кроме двоичного поиска ничего не вспоминаю...
ведь 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

Оценка алгоритмов Найти похожие ветки