Cho biết độ phức tạp của đoạn mã sau giả dùng ký hiệu big-O.s <- 0for i <- 1 to n dos <- s + a[i]for j <- 1 to m dos <- s + b[j]a.O( n )b.O(mn)c.O(m)d.O(m+n)Clear my choice
Question
Cho biết độ phức tạp của đoạn mã sau giả dùng ký hiệu big-O.s <- 0for i <- 1 to n dos <- s + a[i]for j <- 1 to m dos <- s + b[j]a.O( n )b.O(mn)c.O(m)d.O(m+n)Clear my choice
Solution
Đoạn mã trên có độ phức tạp là O(n + m).
Lý do là vì có hai vòng lặp độc lập: vòng lặp đầu tiên chạy từ 1 đến n, và vòng lặp thứ hai chạy từ 1 đến m. Do đó, thời gian chạy tổng cộng của đoạn mã này sẽ là tổng thời gian của cả hai vòng lặp, tức là O(n + m).
Vì vậy, đáp án chính xác là d. O(m + n).
Similar Questions
Cho biết độ phức tạp của đoạn mã giả sau dùng ký hiệu big-O.s = 0for (i = 1; i <= n; i *= 3)s = s + a[i]a.O( n )b.O(n^2)c.O(logn)d.O(nlogn)Clear my choice
Cho biết độ phức tạp của đoạn mã giả sau dùng ký hiệu big-O.int fun(int n)if (n <= 1)return nreturn 2 * fun(n − 1)a.O(logn)b.O(n^2)c.O(nlogn)d.O( n )Clear my choice
Cho biết độ phức tạp của đoạn mã giả sau dùng ký hiệu big-O.x = 0for i <- 1 to n dox++a.O(n^2)b.O(logn)c.O(nlogn)d.O( n )Clear my choice◄ Lab2 - Divide and Conquer
Cho biết độ phức tạp của đoạn mã giả sau dùng ký hiệu big-O.int fun(int n)if (n <= 1)return nreturn fun(n − 1) + fun(n − 1)a.O(2^n)b.O(2^(n/2))c.O(n^2)d.O( n )Clear my choice◄ Lab2 - Divide and Conquer
Ví dụ: Cho tập hợp A=(1,2,3,4)1. Có bao nhiêu nhóm có 3 chữ số khác nhau được xây dựng từ 4 chữ số trên?2. Có bao nhiêu nhóm có 3 chữ số được xây dựng từ 4 chữ số trên?3. Có bao nhiêu nhóm có 4 chữ số được xây dựng từ tập A?
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.