Стратегията Разделяй и владей – анализ на времето за изпълнение
Анализ на времето на изпълнение:
= време за изпълнение на частите + константно време на излъчване крайния резултат: T(N)= 2T(N/2) +O(N).
Теорема:Реш.на уравн.T(N)=аT(N/b)+O(Nk) а>=1; b >1 (а – броят на зад.; в – частите) е:
Това са и 3 случая на рекурентно разбиване на задача на подзад. Напр. сортировка чрез разделяне и сливане : a=b=2; k=1. Имаме втория случай и отговор: O(NlogN)
Ако имаме 3 проблема и всеки е над половината данни и комбинирането за краен резултат изисква O(N) време, то a=3,b=2, k=1. log 2 3 1.59
Имаме случай 1 и O(N )= O(N ) Ако в горния пример времето за обединяване на резултата беше O(N ² ),то сме във случай 3 и: O(N²)
Разделяй и владей -Прoблемът“на-близкостоящи точки”
Имаме Р точки в равнината, p1=(x1,y1)…..
Разстоянието м/ду тях :[(x1 –x2)² + (y1-y2)² ] Търсим най-близкостоящите точки.
Имаме N(N-1)/2 разстояния. Пълен тест: O(N ² ) Друг подход: Нека точките са сортирани по x координатата си. Ако не са, допълнително време
O(NlogN):
Разделяме ги по вертикала на 2 равни части P L P R:
dl и dr могат да се изчислят рекурсивно ( O(NlogN) . Остава да изчислим dc за O(N) време и да постигнем: O(NlogN) +O(N) Нека δ=min(dl,dr). Ще изчисляваме dc само ако подобрява б. Точките в лентата са малко: една по една ( O(N) ):
//points are all in the strip for(I=0;I< numPoinsInStrip; I++) for (j=I+1; j
Сподели с приятели: |
