나는 올바른 장소에 내 질문을 희망, 그리고 또한 그것이 분명 희망입니다병렬 처리가 특정 알고리즘의 복잡성을 변경합니까?
내 질문에, 나는 병렬 알고리즘을 연속 버블 정렬 알고리즘을 변환하고 싶습니다, 내 질문은, 내가 그것을 변환하는 경우 않습니다 복잡성은 여전히 O (n^2)입니까?
그렇다면 순차 알고리즘과 병렬 알고리즘 간의 차이점은 무엇입니까? 나는 병렬로 지시가 한 번에 다른 코어에서 작동한다는 것을 알고 있지만, 다른 것은 시간 뿐인가?
어쩌면 내 질문처럼 stupied : D하지만 난 과거에 병렬 처리가 작동하지 않았다, 그래서 난 내가 좋은 답변
당신을 감사
을 얻을 것이다 바랍니다!Cormen에서보세요 : https://mitpress.mit.edu/sites/default/files/titles/sample/0262533057chap27.pdf
예, 아마도 그것을 병렬화하기 전에 알고리즘의 복잡성, 지금의 "를 자랑한다 무엇 이건 적어도 의미에서, 알고리즘의 점근 동작을 변경해야합니다 over P ", 여기서 P는 코어/쓰레드/태스크의 수입니다. 그래서 복잡성이 변합니다.
위에서 언급 한 CLRS 장의 좋은 점은 아주 좋은 병합 정렬 예제를 포함하여 여러분에게 관심의 대상이 될 수있는 의사 코드 (pseudo-code of algos)가 있다는 것입니다. 또한 MIT의 Leiserson (CLRS의 "L")의 스핀 오프 (spin-off)에 의해 처음 구현 된 실제 "동적 멀티 스레딩 (Dynamic Multithreading)"모델을 제안합니다. (CilkPlus), 그리고 마침내 GCC의 메인 브랜치에서 5.1로 병합되었습니다.
이것은 물론 이론적 인 것으로 사실상 P의 속도 향상은 실제적으로 매우 어렵습니다.