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

11

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

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.n2)
  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.nlognlogn

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

Gil
źródło

Odpowiedzi:

9

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/lognlognlognn/lognlogn

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.)n1+ϵϵ>0

Yuval Filmus
źródło
Celem było znalezienie maksimum w czasie , a nie O ( log n )O(1)O(logn)
NightRa
Weź na siebie, aby udowodnić dolną granicę dla liczby komputerów pomnożonej przez złożoność czasu. Ω(n)
Yuval Filmus