Влияние върху производителността

if(dist(pi,pj) <б) б = dist(pi,pj);

for(I=0; I
for( j=I+1; j< numPointsInStrip; j++)

if (pi and pj ’coordinates differ by more than б) break; // next pi.

else

if(dist(pi,pj)<б) б = dist(pi,pj);

само p4 и p5 се разглеждат, съобразно горната модификация:

най-много 7 т. могат да се разглеждат в правоъгълната област б
*2б:

30. Теоретични подобрения на аритметичните операции.Анализ

* Умножение на цели числа

• 
  За малки ч-ла - линейно време.
  
• 
  За големи, времето става квадратично.
  

Нека имаме N р-дни ч-ла X и Y. Знакът определяме лесно. По класически алгоритъм O(N ² ) : всяка цифра на X се умножава по всяка на Y.
Времето за това < O(N).
Имаме О(NlogN) от рекурсивните повиквания отляво и отдясно + O(N).
За сортирането по у е нужно още O(NlogN) за всяко рекурсивно повикване или общо O(Nlog ² N). (пълно претърсване: O(N ² ).
Mожем още да ускорим като предварително сортираме и по x и по у и изработим 2 списъка с точки, сортирани съответно. ( O(NlogN) време в началото ). После претърсваме списъка по x и махаме всички точки с коорд. > б. Автоматично остават само тези в линията и то сортирани по у. Това изисква O(N). общо време O(NlogN) +O(N)

Имаме 4 умножения с N/2 цифри:
T(N)= 4T(N/2) + O(N)
според теоремата в началото това е:O(N²) - нямаме подобр.Трд намал броя умнож:

Изтегляне 1.47 Mb.

Сподели с приятели: