Влияние върху производителността
Xl Yr+Xr Yl=(Xl–Xr)(Yr–Yl)+Xl Yl+Xr Yr
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
- Навигация на страницата:
- Динамично програмиране – таблици вместо рекурсия
- Ускоряване на сортировката с паралелизми чрез стратегия разделяй и владей.
Xl Yr+Xr Yl=(Xl–Xr)(Yr–Yl)+Xl Yl+Xr YrУмножение на матрици Ето стандартен алгоритъм с O(N ³) време. Matrix
|
|
M1= |
(A12-A22)(B21+B22) |
Резултатът се получава така: |
|
M2= |
(A11+A22)(B11+B22) |
C11= M1+M2-M4+M6 |
|
M3= |
(A11-A21)(B11+B12) |
C12= M4+M5 |
|
M4= |
(A11+A12)B22 |
C21= M6+M7 |
|
M5= |
A11(B12-B22) |
C22= M2-M3+M5-M7 |
|
M6= |
A22(B21-B11) |
T(N)=7T(N/2)+O(N)=O( Nlog²7 )=O( N ².81 ) |
|
M7= |
A21+A22)B11 |
|
Динамично програмиране – таблици вместо рекурсия
Рекурсията не е оптималната техника в ред случаи рек. алгоритъм следва а се пренапише в нерекусивен вариан със запомняне межд. резултати в таблица.
Една техника за това е “динамичното програмиране”.
таблици вместо рекурсия. Ето неефективен вариант за изчисляване ч-лата на Фибоначи:
int fib( in n)
{ if( n <= 1 ) return 1;
else return fib( n – 1 ) + fib( n – 2 ); }
T(N) >= T(N-1) +T(N-2)
сложностa e експоненциална. Мд съхраним изчислените вече F n-1; F n-2. :
int fibonacci( int n )
{ if( n <= 1 ) return 1; int last = 1;
int nextTolast = 1; int answer = 1;
for( int I = 2; i <= n; i++ )
{ answer = last + nextTo last; nextTolast = last;
last = answer;
}return answer;}
Имаме O(N). Ако горната модификация не е направена, за изчисление на Fn се вика рекурсивно Fn-1 и Fn-2…..
Ускоряване на сортировката с паралелизми чрез стратегия разделяй и владей.
Динамично програмиране: Оптимално бинарно търсене в дърво.
Рекурсията не е оптималната техника в ред случаи рек. алгоритъм следва а се пренапише в нерекусивен вариан със запомняне межд. резултати в таблица. Една техника за това е “динамич.програмиране”.
oптимално бинарно търсене в дърво
Имаме списък думи w1……wn с вероятности на появяване: p1…..pn
Искаме да подредим думите в бинарно дъво, така че общото време за намиране на дума да min. В бинарно д-во за да стигнем до ел. с дълбочина d, правим d+1 сравнения. Така че, ако wi е на дълбочина di, ние искаме да минимизираме
първото използва greedy стратегия. Най-вероятната дума е най-горе. Второто е балансирано search tree (в дясно с по-ниско pi).Третото е оптималното – виж табл
сравнение на 3 дървета с бинарно търсене
При optimal binary search tree данните не са само в листата (Hofman) и следва да удовлетворяваме критерий за binary search tree.
Поставяме сортирани според някакъв критерий думи wleft, wleft+1,….wright-1, wright в бинарно дърво. Нека сме постигнали оптималното бинарно дърво в което имаме корен wi и поддървета за които : Left <= i <- Right. Тогава лявото поддърво съдържа елементите wleft, …w i-1, а дясното – wi+1,……wright ( критерий за binary search tree ).
Поддърветата също правим оптимал. Тогава можем да напишем формулата за цената Cleft,right на оптимално binary search tree. Лявото поддърво има цена Cleft,I-1, дясното – Ci+1,right спрямо корена си.
На основата на тази формула се гради алг. за цена на оптималното дърво.Търсим i, така че да се минимизира C Left,Right.
Последователно се поставят за корени am, and, egg, if и се изчислява цена и оттам минималната цена. Например, когато and е корен, лявото поддърво am…am има цена 0,18 (вече определена), дясното – egg-if с цена 0.35 и pam+pand+pegg+pif = 0.68.
Тогава общата цена е 1,21.Времето е O(N ³) защото имаме тройно вложен цикъл
Изтегляне 1.47 Mb.
Сподели с приятели: