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
Question
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
Solution
Đoạn mã giả trên có độ phức tạp là O(logn).
Giải thích: Trong vòng lặp, biến i được nhân lên 3 lần sau mỗi lần lặp. Điều này có nghĩa là số lần lặp sẽ tăng lên theo hàm logarit cơ số 3 của n. Do đó, độ phức tạp thời gian của đoạn mã giả này 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.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ã 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.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.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
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.