Phân tích Big O của thuật toán này là gì?

Question

tôi đang làm việc trên một khóa học cấu trúc dữ liệu và tôi không chắc chắn làm thế nào để tiến hành w/O phân tích Big này:

sum = 0; 
for(i = 1; i < n; i++) 
    for(j = 1; j < i*i; j++) 
     if(j % i == 0) 
      for(k = 0; k < j; k++) 
        sum++; 

ý tưởng ban đầu của tôi là điều này là O (n^3) sau khi giảm, vì vòng lặp trong cùng sẽ chỉ chạy khi j/i không còn lại và quy tắc nhân không thể áp dụng được. Lý do của tôi có chính xác ở đây không?

Answer 1

Hãy bỏ qua vòng lặp bên ngoài trong một giây ở đây và chúng ta hãy phân tích nó theo số i.

Vòng lặp giữa chạy i^2 lần, và được gọi vòng lặp bên trong bất cứ khi nào j%i == 0, có nghĩa là bạn chạy nó trên i, 2i, 3i, ...,i^2, và tại mỗi lần bạn chạy cho đến khi có liên quan j, điều này có nghĩa là vòng lặp tổng kết bên trong của thời gian chạy là :

i + 2i + 3i + ... + (i-1)*i = i(1 + 2 + ... + i-1) = i* [i*(i-1)/2] 

Bình đẳng cuối cùng đến từ sum of arithmetic progression.
Ở trên là trong O(i^3).

lặp lại này để các vòng ngoài mà chạy 1-n và bạn sẽ nhận được thời điểm O(n^4) chạy, kể từ khi bạn thực sự có:

C*1^3 + C*2^3 + ... + C*(n-1)^3 = C*(1^3 + 2^3 + ... + (n-1)^3) = 
= C/4 * (n^4 - 2n^3 + n^2) 

Phương trình cuối cùng xuất phát từ sum of cubes
Và ở trên là trong O(n^4), đó là sự phức tạp của bạn.