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
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 2 * fun(n − 1)a.O(logn)b.O(n^2)c.O(nlogn)d.O( n )Clear my choice
Solution
Đoạn mã giả trên có độ phức tạp là O(n).
Lý do là vì mỗi lần gọi hàm fun(), n giảm đi 1. Do đó, số lần gọi hàm fun() tỷ lệ thuận với n.
Vì vậy, đáp án chính xác là d. O(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 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
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 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 )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
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
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.