Phân tích Big-O cho vòng lặp

Question

Tôi phải phân tích vòng lặp này, trong số những thứ khác và xác định thời gian chạy của nó bằng ký hiệu Big-O.

for (int i = 0; i < n; i += 4) 
    for (int j = 0; j < n; j++) 
     for (int k = 1; k < j*j; k *= 2)` 

Dưới đây là những gì tôi có cho đến nay:

for (int i = 0; i < n; i += 4) = n 

---

for (int j = 0; j < n; j++) = n 

---

for (int k = 1; k < j*j; k *= 2) = log^2 n 

Bây giờ vấn đề tôi sắp đến là thời gian chạy cuối cùng của vòng lặp. Đoán tốt nhất của tôi là O (n^2), tuy nhiên tôi không chắc chắn nếu điều này đúng. Có ai giúp được không?

Chỉnh sửa: xin lỗi về Oh -> O điều. sách giáo khoa của tôi sử dụng "Big-Oh"

Answer 1

Lưu ý đầu tiên rằng vòng lặp ngoài độc lập với hai vòng còn lại - nó chỉ đơn giản là thêm một hệ số (n/4)*. Chúng tôi sẽ xem xét điều đó sau.

Bây giờ chúng ta hãy xem xét sự phức tạp của

for (int j = 0; j < n; j++) 
    for (int k = 1; k < j*j; k *= 2) 

Chúng tôi có tổng sau:

0 + log (1) + log (2 * 2) + ... + log (n * n)

Nó là tốt để lưu ý rằng log (n^2) = 2 * log (n). Vì vậy chúng tôi lại yếu tố tổng để:

2 * (0 + log (1) + log (2) + ... + đăng nhập (n))

Nó không phải là rất dễ dàng để phân tích số tiền này nhưng hãy xem this post. Sử dụng xấp xỉ của Sterling có thể là thuộc về O(n*log(n)). Do đó độ phức tạp tổng thể là O((n/4)*2*n*log(n))= O(n^2*log(n))

Answer 2

Thời gian phức tạp của một vòng lặp được coi là O (n) nếu các biến vòng lặp được tăng/giảm đi một lượng không đổi (đó là c trong ví dụ dưới đây):

for (int i = 1; i <= n; i += c) { 
     // some O(1) expressions 
    } 

    for (int i = n; i > 0; i -= c) { 
     // some O(1) expressions 
    } 

Độ phức tạp về thời gian của vòng lặp lồng nhau bằng số lần câu lệnh trong cùng được thực thi. Ví dụ các vòng mẫu sau đây có O (n ²) thời gian phức tạp:

for (int i = 1; i <=n; i += c) { 
     for (int j = 1; j <=n; j += c) { 
      // some O(1) expressions 
     } 
    } 

    for (int i = n; i > 0; i += c) { 
     for (int j = i+1; j <=n; j += c) { 
      // some O(1) expressions 
    } 

Thời gian phức tạp của một vòng lặp được coi là O (logn) nếu các biến vòng lặp được chia/nhân với một lượng không đổi:

for (int i = 1; i <=n; i *= c) { 
     // some O(1) expressions 
    } 
    for (int i = n; i > 0; i /= c) { 
     // some O(1) expressions 
    } 

Bây giờ chúng ta có:

for (int i = 0; i < n; i += 4) <----- runs n times 
    for (int j = 0; j < n; j++) <----- for every i again runs n times 
     for (int k = 1; k < j*j; k *= 2)` <--- now for every j it runs logarithmic times. 

Vì vậy, độ phức tạp là O (n²logm) trong đó m là n² có thể được đơn giản hóa thành O (n²logn) vì n²logm = n²logn² = n² * 2logn ~ n²logn.

Answer 3

• Về j, vòng lặp bên trong là O(log_2(j^2)) thời gian, nhưng sin log_2(j^2)=2log(j), nó thực sự là O(log(j)).

• Đối với mỗi lần lặp của vòng lặp giữa, phải mất O (log (j)) thời gian (để làm vòng lặp bên trong ), vì vậy chúng ta cần phải tổng hợp:

  sum {log (j) | nhật ký j = 1, ..., n-1} (1) + nhật ký (2) + ... + nhật ký (n-1) = log ((n-1)!)

Và kể từ log((n-1)!) là trong O((n-1)log(n-1)) = O(nlogn), chúng tôi có thể kết thúc vòng giữa ở giữa có các hoạt động O(nlogn).

• Lưu ý rằng cả hai vòng giữa và bên trong là độc lập của i, vì vậy để được tổng độ phức tạp, chúng tôi chỉ có thể nhân n/4 (số lặp đi lặp lại của vòng lặp bên ngoài) với độ phức tạp của vòng lặp giữa, và nhận được:

  O (n/4 * nlogn) = O (n^2logn)

Vì vậy, tổng độ phức tạp của mã này là O(n^2 * log(n))