Алгоритмы для параллельных вычислений
Есть такая задачка (на английском) по параллельным исчислениям. Надо найти алгоритм.
Write a PRAM algorithm to find the longest consecutive (continuous)
sequence of 1's in a binary array. It is enough to return the starting index of the sequence. E.g., for array [1 0 1 1 1 1 0 1 0 0 0 0 0 1] the return value would be 3 (2 if you use 0-indexed arrays). You may assume a convenient input size. You may not use CRCW PRAM. State the execution time, number of processors used and work of your algorithm.
Тhe algorithm should be O(logN) time and O(N) work.
__________________
Лучше поздно, чем никогда. Но лучше поздно, чем сейчас...
.....oooO..............
.....(....)...Oooo.....
......\..(.....(....).....
.......\_).....)../......
...............(_/.......
Я бы изменил мир, но Бог не дает исходники...
|