Giúp giải bài tập tìm độ phức tạp của thuật toán

#1

1.png1360×555 15.8 KB

Em học đến phần tìm độ phức tạp của thuật toán mà nhìn mãi chẳng hiểu các đếm số lần lặp ai xem giúp em

1 Like
#2

b) Vòng for đầu biến i chỉ chạy đến 3, i không đáng kể nếu như n rất lớn
3n => O(n)

EDIT:
d) Trường hợp này thì có tổng cộng (n^2- n)/2 => O(n^2)

Thường thì mình chỉ lấy bậc lớn nhất cho đơn giản, ví dụ như trường hợp d). Vì giả sử như n rất lớn (10^9) thì lúc đó n so với n^2 không đáng kể
Bạn có thể tham khảo thêm vể độ phức tạp của 1 số thuật toàn thông dụng ở đây http://bigocheatsheet.com/

2 Likes
#3

Sao anh lấy được n*(n-1) đấy :frowning: em chả hiểu gì huhu

#4

Em thử n = 9 thì ra 36 mà thay 9 vào n*(n-1) thì ra 72 mà :frowning:

#5

à, xin lỗi bạn. Lúc nãy mình đọc không kĩ, j chạy từ i+1 thì độ phức tạp vẫn là O(n^2) cho d).

Với n >=2:
i=1: j lặp n-1
i=2: j lặp n-2
…
i=k: j lặp n-k
…
i=n-1: j lặp 1

Tổng số vòng lặp sẽ có dạng: (n - 1) + (n - 2) + … (n-k) + 1
<=> n^2 - (1+2+…+ k +…+ n)
<=> n^2 - n*(n+1)/2
<=> (n^2- n)/2

Độ phức tạp vẫn là O(n^2)

1 Like
#6

Bạn đang đánh giá độ phức tạp của thuật toán, ở đây chỉ xét đơn giản là nó bằng số phép tính cơ bản được thực hiện.

Ở câu b, phép tính cơ bản ở đây là sum++, i chạy từ 0 đến 3, và mỗi i sẽ có n phép tính được thực hiện, như vậy tổng cộng có 3*n phép tính nên độ phức tạp là O(3n) = O(n).

Ở câu c, phép toán cơ bản có thể chọn 1 trong 3 cái phép gán kia, ứng với mỗi i thì phép toán sẽ có n-i -1 phép tính cơ bản được thực hiện (i = 1 thì cái vòng for trong thực hiện n-1-1 lần, i = k thì nó thực hiện n-k-1 lần), như vậy tổng cộng có (n-1) + (n-2) +.. + (n-k-1) + ... +1 = n*(n-1) / 2. Do vậy độ phức tạp là O(n(n-1)/2) = O(n^2)

1 Like
#7

a) => O(n)
b) => O(n^2)

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?