Hỏi về độ phức tạp của vòng for

#1

Trường hợp:

int n = 10;
for (int i = 2; i <= n; i++)
{
     // Khối lệnh
}

thì độ phức tạp là sao ạ?
Em cảm ơn.

#2

Số vòng lặp ở for là n - 1 (n - 2 + 1), rút lại được O(n). Giả sử khối lệnh bên trong nó có độ phức tạp là O(1) thì độ phức tạp của thuật toán trên là O(n).

3 Likes
#3

Trường hợp trong for có nhiều hơn 1 khối lệnh là 3 khối lệnh thì mình chỉ xét số lần của phép toán tích cực không quan tâm đến phép toán khác hay sao ạ?

#4

Do lệnh tăng 1 và xét điều kiện là O(1) rồi bạn, chứ vẫn có tính :smiley:

4 Likes
#5

Em vẫn chưa hiểu lắm ạ :sweat_smile:
Trường hợp

for (int i = 3; i <= n; i++)
{
    // Khối lệnh 1
    // Khối lệnh 2
    // Khối lệnh 3
}

thì sẽ là 3.(n - 3 + 1) = 3.(n-2) = O(n) phải ko ạ?
Em cảm ơn!

1 Like
#6

Đúng ra phải là:

  • Số lần lặp for là f_{for} = \frac{n-3}{1}+1=n-2 (phép tăng i++ có độ phức tạp O(1)).

  • Gọi độ phức tạp của khối lệnh i là O(f_i(n))

Vậy độ phức tạp của vòng lặp for này là O(f_{for}(n) * \Sigma f_i(n)) = O(n\ \Sigma f_i(n))

Bạn không nói 3 khối lệnh này làm gì nên không thể đánh giá chúng là O(1) được.

3 Likes
#7

Dạ. Nếu 3 khối lệnh đó là phép gán thì sẽ là O(n*3) sử dụng quy tắc bỏ hằng số thì sẽ là O(n) đúng không ạ?

#8

Đúng rồi cậu. Cậu nắm được rồi đấy! :smile:

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