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
Question
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
Solution
Đoạn mã giả trên có độ phức tạp là O(logn).
Giải thích: Đoạn mã giả trên là một hàm đệ quy, trong đó mỗi lần gọi đệ quy, giá trị của n sẽ giảm đi một nửa. Do đó, số lần gọi đệ quy sẽ tương ứng với số lần chia n cho 2 cho đến khi n <= 1. Điều này tương đương với việc tìm số lượng các số nguyên từ 1 đến n trong hệ số 2, tức là log2n. Do đó, độ phức tạp của đoạn mã giả trên là O(logn).
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 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ã 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.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ã 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.