Algorytm równoległy do ​​znalezienia maksymalnego czasu przy użyciu procesorów

Zostaliśmy zaprezentowani w klasie z algorytmem znajdowania maksimum w tablicy równolegle w złożoności czasowej z komputerami.$O(1)$$n^2$

Algorytm był:

Biorąc pod uwagę tablicę A o długości n:

1. Utwórz tablicę flag B o długości n i zainicjuj ją zerami z komputerów.$n$
2. Porównaj co 2 elementy i napisz 1 w B przy indeksie minimum z komputerami.$n^2$
3. znajdź indeks z 0 w A przy komputerach.$n$

Wykładowca drażnił nas, że można tego dokonać na komputerach i przy złożoności czasu.$\frac{n}{\log n}$$\log n$

Po wielu myślach nie mogłem wymyślić, jak to zrobić. Dowolny pomysł?

Podziel oryginalną tablicę na bloków długości . Ustaw każdy procesor za każdy blok i znajdź maksimum przy użyciu zwykłego algorytmu w czasie . Teraz musimy obliczyć maksimum tablicy o długości . Sparuj elementy i oblicz maksima parami, aby zmniejszyć rozmiar tablicy o połowę. Powtórz razy, aby znaleźć maksimum całej tablicy.$n/\log n$$\log n$$\log n$$n/\log n$$\log n$

Ten sam pomysł pokazuje również, że można obliczyć maksimum równolegle w stałym czasie za pomocą komputerów dla każdego . (Ćwiczenie.)$n^{1+\epsilon}$$\epsilon > 0$