�ݺ�ߣ

CV_RTF: algo posidelky
«Оценка сложности алгоритмов»

Зачем?
Ограниченность ресурсов:
•Время
•Память

Как оценить скорость?

В MatLAB есть специальный инструмент
Код:
A = ones(500,500);
B = ones(500,500) * 2;
C = zeros(500,500);
tic
C = A .* B;
toc
% ======
tic
for i = 1 : 500
for j = 1 : 500
C(i,j) = A(i, j) * B(i, j);
end
end
toc

В MatLAB есть специальный инструмент
Вывод:
Elapsed time is 0.000822 seconds.
Elapsed time is 0.008758 seconds.

В С++ можно написать костыль!
#include <ctime>
…
clock_t time = clock();
// algorithm
double delta = (double)(clock() – time);
delta /= CLOCKS_PER_SEC;
cout << “Time is ” << delta << endl;
…

В общем случае вы за[fail]итесь, потому что:
•Входные данные разные
•Реализация железа разная
Компания Reca выпускает мониторы, большой популярностью пользуется их модель
AB999 с размерами экрана a × b сантиметров. Из-за особенностей
производства, размеры экрана выражаются целым числом сантиметров. Недавно в
моду вошло соотношение сторон x: y. Компания хочет уменьшить размеры экрана
своего монитора AB999 так, чтобы его соотношение сторон стало x: y, но при этом его
площадь была максимально возможной. Ваша задача — определить размеры экрана
уменьшенной модели, или выяснить, что это сделать невозможно.

В первой строке входных данных содержатся 4 целых числа — a, b, x и y
(1≤a,b,x,y≤2·109).
http://codeforces.ru/problemset/problem/16/C

Реализация алгоритма Евклида на Python:
def gcd(a,b):
while a != b:
if a > b:
a = a - b
else:
b = b - a
print(a)

Скорость выполнения определённой инструкции
Разрядность архитектуры
Векторное ускорение вычислений
И т.д. и т.п.

Более математически: О-нотация
O(g) - множество функций f, для которых существуют
такие константы C и N, что |f(x)| ≤ C|g(x)| для всех x > N.
Запись f = O(g) дословно обозначает, что f принадлежит множеству O(g). При
этом обратное выражение O(g) = f не имеет смысла.
По сути, наша задача: описать поведение функции в зависимости от
параметра.

Рассмотрим алгоритм вычисления значения
многочлена степени n в заданной точке x.
Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x + a0

Вычисление i-го слагаемого (i=1..n) требует i
умножений. Значит, всего
1 + 2 + 3 + ... + n = …

1 + 2 + 3 + ... + n = n(n+1)/2
Кроме того, требуется n+1 сложение.

1 + 2 + 3 + ... + n = n(n+1)/2
Кроме того, требуется n+1 сложение. Всего
n(n+1)/2 + n + 1= n2/2 + 3n/2 + 1
операций.

Каково поведение функции?
f(n)= n2/2 + 3n/2 + 1

Каково поведение функции?
f(n)= n2/2 + 3n/2 + 1
Поведение: O(n2) “Большое О от эн квадрат”

Это верхняя оценка, т.е количество операций (а значит, и
время работы) растет не быстрее, чем квадрат количества
элементов. Чтобы почувствовать, что это
такое, посмотрите на таблицу, где приведены
числа, иллюстрирующие скорость роста для нескольких
разных функций.

n

log n

n * log n

n^2

1

0

0

1

16

4

64

256

256

8

2048

65536

4096

12

49152

16777216

65536

16

1048565

4294967296

1048576

20

20969520

1,0993E+12

16775616

24

402614784

2,81421E+14

n

log n

n * log n

n^2

1

0

0

1

16

4

64

256

256

8

2048

65536

4096

12

49152

16777216

65536

16

1048565

4294967296

1048576

20

20969520

1,0993E+12

16775616

24

402614784

2,81421E+14

Пусть операция длится 3 нс = 3*10-9 с, тогда для n =224
t = (2.81 * 1014) * (3 * 10-9) = 3 * 2.81 * 105 c ~ 10 дней

Правила
•При оценке за функцию берется количество
операций, возрастающее быстрее всего.
•При оценке O() константы не учитываются.

Пример хитрожопости:
Геометрическое размытие
~28 Mpx (4800 x 6000 px)
O(?)

~28 Mpx (4800 x 6000 px)
Сложность О(N2 D2)


Прямой метод: 457 сек

Прибл. метод: 31 сек

Прибл. метод: 3 сек

Есть ещё L-нотация
http://ru.wikipedia.org/wiki/L-нотация
L-нотация — это асимптотическая
нотация, аналогичная О-нотации, записывается как
Ln[a,c] для n стремящимся к бесконечности. Подобно
O-большому, нотация обычно используется для грубой
оценки вычислительной сложности определенного
алгоритма.

�ݺ�ߣ

Algo 01 part01

Recommended

More Related Content

What's hot (20)

Similar to Algo 01 part01 (20)

Algo 01 part01