Bài giảng Tính toán song song và phân toán - Chương 6: Đánh giá thuật giải song song cung cấp cho các bạn những kiến thức về độ phức tạp thời gian, Speedup, Efficiency, định luật Amdahl, chi phí thời gian. | 11/16/12 6. Đánh giá thuật giải song song Tính toán song song và phân tán . Trần Văn Lăng 1. 2. 3. 4. 5. tvlang@vast-‐ lang@ 1 Độ phức tạp thời gian Speedup Efficiency Định luật Amdahl Chi phí thời gian 2 Độ phức tạp thời gian • Để đánh gía thuật giải song song thường căn cứ vào: – Thời gian Ynh toán (hay Time Complexity) – Yêu cầu số bộ xử lý (hay Processor Complexity) • T(n) = O(f(n)) nếu có số dương C và n0 sao cho T(n) n0 • T(n) = Ω(f(n)) nếu có số dương C và n0 sao cho T(n) > Cf(n), với các n > n0 1 11/16/12 Ngoài ra, • T(n) = θ(f(n)) nếu có các số dương C1, C2, n1, n2 sao cho T(n) n1 và T(n) > C2f(n), với tất cả các n > n2. • Khi đó T(n) = θ(f(n)) nếu và chỉ nếu T(n) = O(f(n)) và T(n) = Ω(f(n)) • Và, T(n) = O(f(n)) tương đương f(n) = Ω(T(n)) • T(n) = o(f(n)) nếu với mọi số dương C, tồn tại n0 sao cho T(n) n0 • T(n) = ω(f(n)) nếu với mọi số dương C, tồn tại n0 sao cho T(n) > Cf(n), với các n > n0 Khi đó, • T(n)=o(f(n)) tương đương f(n)= ω(T(n)) • T(n)=o(f(n)) suy ra T(n)=O(g(n)) • T(n)= ω(f(n)) suy ra T(n)= Ω(f(n)) • Một thuật giải bao gồm 2 phần, phần thứ nhất có độ phức tạp là O(f1(n)), phần thứ hai là O(f2(n)). • Khi .
