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
Question
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
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 đệ quy, hàm sẽ gọi lại chính nó hai lần với tham số giảm đi 2. Do đó, số lượng lời gọi đệ quy sẽ tăng theo cấp số nhân, dẫn đến độ phức tạp của đoạn mã là O(2^n).
Vì vậy, đáp án chính xác là b. 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 func(int n)if (n <= 1)return 0elsereturn func(n/2) + 1a.O(n^2)b.O(nlogn)c.O( n )d.O(logn)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 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ã 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.