Độ phức tạp tính toán trong một chương trình xử lý song song

Có hai tham số là:

  1. Số lượng các phần tử: n
  2. Số lượng processors: k

Ví dụ:

  1. Bài toán tính tổng các số từ 1 tới n và Bài toán tìm vị trí các phần tử có giá trị bằng v có độ phức tạp về thời gian là: O(n/k)
  2. Bài toán sắp xếp QuickSort sử dụng thuật toán song song có độ phức tạp là: O(n/klog(n/k)) + O(k*n)

Điều đó có nghĩa: Thường thì độ phức tạp thời gian nhỏ hơn so với việc dùng 1 processor. Nếu ta cố định số lượng processors nhỏ hơn một giá trị v cho trước thì cho dù có song song thì độ phức tạp về thời gian vẫn là O(n) hoặc O(nlogn) cho hai trường hợp ở trên.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: