Phân tích các thuật toán cho độ phức tạp thời gian

Question

Tôi đang phân tích một thuật toán và tôi chỉ muốn biết liệu tôi có đi đúng hướng hay không.

Đối với thuật toán này, tôi chỉ tính các phép nhân trên dòng có *** trong chúng.

Dưới đây là các thuật toán:

1. Vì vậy, tôi bắt đầu từ dòng hầu hết bên trong, tôi có thể thấy có 2 hoạt động ở đó (hai phép nhân).
2. Bây giờ tôi đang xem xét 2 vòng bên trong nhất, vì vậy tôi có thể nói rằng p=p*20*z được thực thi chính xác (j) + (j-1)+(j-2)+(j-3)...1 lần. Điều này xảy ra bằng j(j+1)/2.
3. Vì vậy, trong tổng số, vì có hai phép nhân, nó xảy ra 2 * (j(j+1)/2).
4. Sau đó, vòng lặp "i" xảy ra chính xác n lần, vì vậy, tổng cộng, đó là n(2 * (n(n+1)/2)).

Đó là quá trình suy nghĩ của tôi sau này. Tôi có đúng không? Cảm ơn.

Answer 1

Quy trình suy nghĩ của bạn là chính xác. Bạn cần thay cụm từ j bằng n (n là giá trị lớn nhất j có thể giả định), nhưng đó có thể là lỗi đánh máy.

Bên cạnh đó, bạn có thể đơn giản hóa hơn nữa từ bạn đang ở đâu:

n(2*(n(n+1)/2)) 
2*n*(n^2+n)/2 
n^3+n^2 

=> O(n^3) 

Bước cuối cùng là do hạn n cubed sẽ tăng trưởng với tốc độ lớn hơn nhiều so với n bình phương hạn chúng ta có thể nói rằng nó sẽ chiếm lĩnh thời gian chạy cho n lớn. Chỉ có điểm khác tôi sẽ đề cập đến là bạn có lẽ nên xem xét các cửa hàng để p như một hoạt động cũng như hai phép nhân, mặc dù rõ ràng điều này sẽ không thay đổi thời gian chạy đơn giản-o lớn.

Answer 2

Tính trong ví dụ cụ thể này có thể được đơn giản nếu bạn có thể tìm ra rằng tất cả ba vòng có điều kiện thoát cùng up to n:

1. i <= n
2. j <= n
3. k <= j

Về cơ bản vòng lặp thứ ba cũng sẽ chạy các lần lặp lại n cũng vì j <= n để k <= n, này có nghĩa là sự phức tạp đó sẽ là n * n * n = O(n^3)

Answer 3

Đây là cách bạn có thể có được thứ tự của sự phát triển của thuật toán của bạn có phương pháp: