시퀀스 정렬 여부를 확인하는 병렬 알고리즘

Question

주어진 n 개의 시퀀스가 ​​정렬되어 있는지 확인하려면 병렬 알고리즘 (비용 최적화)이 필요합니다.

Answer 1

m 개의 스레드의 경우, 각 스레드에 n/m 개의 연속 번호가 겹치고 1 개의 번호가 겹치도록하십시오. 각 스레드에서 할당 된 순서가 정렬 된 순서인지 확인하십시오. 모든 서브 시퀀스가 ​​정렬되면 전체 시퀀스가 ​​정렬됩니다.

예 :

[1, 4, 5, 6, 11, 42] => [1, 4, 5, 6*] and [6, 11, 42] with 2 threads 
[1, 4, 5, 6, 11, 42] => [1, 4, 5*], [5, 6, 11*] and [11, 42] with 3 threads 

*이 1.

용액에서 오버랩된다 복잡도 O (N/m)를 갖는다.