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
Question
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
Solution
Đoạn mã giả trên có độ phức tạp là O(2^n).
Giải thích: Đoạn mã giả trên là một hàm đệ quy, trong đó mỗi lần gọi hàm, nó sẽ gọi lại chính nó hai lần với giá trị n giảm đi 1. Do đó, số lượng lời gọi hàm sẽ tăng theo cấp số nhân, tức là 2^n.
Vì vậy, đáp án chính xác là a. O(2^n).
Similar Questions
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 F(int n)if (n <= 2)return 1elsereturn F(n − 2) * F(n − 2)a.O(2^(n/2))b.O(2^n)c.O(n^2)d.O( n )
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ã 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
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.