Độ phức tạp của chức năng của tôi là bao nhiêu?

Question

Bắt đầu nghiên cứu về tính phức tạp, tôi đang vật lộn với cái này:

void what(int n) { 
    int i; 
    for (i = 1; i <= n; i++) { 
     int x = n; 
     while (x > 0) 
      x -= i; 
    } 
} 

Vâng, là người đầu tiên cho vòng lặp rõ ràng là O(n). Lần lặp đầu tiên là O(n), số thứ hai là O(n/2) .. và như vậy là log(n) lần tôi đoán? Có nghĩa là O(n) * O(log(n)) = O(n * log(n)) complexity. Tôi đã nhận được quyền này?

Chỉnh sửa: (không trùng lặp) Tôi biết Big O là gì. Tôi đã yêu cầu đánh giá chính xác trong một trường hợp cụ thể.

Answer 1

Vòng lặp ngoài chạy n lần.

Đối với mỗi lần lặp lại, vòng lặp bên trong chạy n/i lần.

Tổng số chạy là:

n + n/2 + n/3 + ... + n/n 

tiệm (bỏ qua nguyên số học làm tròn), điều này giúp đơn giản hoá như

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

Loạt bài này lỏng lẻo hội tụ về phía n * log(n).

Do đó độ phức tạp là O (N.log (N)) như bạn mong đợi.

Answer 2

Các vòng lặp bên trong đầu tiên chạy n lần
Các vòng lặp bên thứ hai chạy n/2 lần
Các vòng lặp bên thứ ba chạy n/3 lần
.. Người cuối cùng chạy một lần

Vì vậy n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n).

Đây là n nhân với tổng của chuỗi hài hòa, không có biểu diễn dạng đóng kín. Nhưng như được hiển thị here nó là O(log(n)). Vì vậy, tổng thể thuật toán là O(n log(n))

Answer 3

Thử điều này bằng thử nghiệm và đồ họa. Lôgic log2 vs log2 trông khá tuyến tính. Một cái gì đó giữa nhiều hơn O tuyến tính (n) và ít hơn O (n * log (n)). "Vẽ" kết luận của riêng bạn.

[Chỉnh sửa]

Sử dụng các công thức có nguồn gốc toán học, O() tính là một giới hạn trên của O (n * log (n)). Điều đó sử dụng "phân số lặp vòng lặp" giúp tăng số lượng theo một phần nhỏ chứ không phải 1. Ví dụ: Khi n là 6, số lần lặp là 6 + 3 + 2 + 1.5 + 1.2 + 1 = 14.7 vòng thay vì thực tế 6 + 3 + 2 + 2 + 2 + 1 = 16. Sự khác biệt này tương đối ít quan trọng hơn khi tăng n, do đó sự tăng trưởng ít hơn O (n * log (n)). Vì vậy, bằng cách không bỏ qua mã sử dụng toán học số nguyên, chúng tôi có một câu hỏi khó khăn hơn nhiều.

---

unsigned long long what(int n) { 
    unsigned long long cnt = 0; 
    int i; 
    for (i = 1; i <= n; i++) { 
    int x = n; 
    while (x > 0) { 
     x -= i; 
     cnt++; 
    } 
    } 
    return cnt; 
} 

void wtest(int n) { 
    unsigned long long cnt = what(n); 
    printf("%d %llu\n", n, cnt); 
    fflush(stdout); 
} 

void wtests(void) { 
    int i = INT_MAX/2 + 1; 
    while (i > 0) { 
    wtest(i); 
    i /= 2; 
    } 
} 

int main(void) { 
    wtests(); 
    return 0; 
} 

Output

1073741824 23567395117 
536870912 11411566988 
268435456 5519718329 
134217728 2666826555 
67108864 1286897093 
33554432 620190504 
16777216 298466265 
8388608 143418602 
4194304 68802063 
2097152 32947406 
1048576 15746897 
524288 7510048 
262144 3573331 
131072 1695816 
65536 802493 
32768 378537 
16384 177921 
8192 83286 
4096 38803 
2048 17973 
1024 8275 
512 3782 
256 1713 
128 765 
64 337 
32 145 
16 61 
8 24 
4 9 
2 3 
1 1 

Answer 4

Là một thay thế, sử dụng một biến thay y = n - x Tiếp theo ký hiệu Sigma để phân tích số lần lặp lại của while vòng lặp bên trong của thuật toán của bạn .

Các ước lượng quá ở trên, đối với mỗi bên trong vòng lặp while, số lần lặp lại bởi 1 đối với trường hợp n-1 không phải là một bội số của i, ví dụ nơi (n-1) % i != 0. Khi chúng tôi tiến hành, chúng tôi giả định rằng (n-1)/i là một số nguyên cho tất cả các giá trị i, do đó đánh giá quá cao tổng số lần lặp trong vòng lặp while bên trong, sau đó bao gồm dấu nhỏ hơn hoặc bằng nhau tại (i) bên dưới. Chúng tôi tiến hành phân tích ký hiệu Sigma:

nơi chúng tôi, tại (ii), đã xấp xỉ n: thứ harmonic number bởi không thể thiếu đi kèm. Do đó, thuật toán của bạn chạy trong O(n·ln(n)), tiệm cận.

---

Rời hành vi tiệm cận và nghiên cứu sự phát triển thực tế của thuật toán, chúng ta có thể sử dụng dữ liệu mẫu đẹp chính xác (n,cnt) (nơi cnt là số lần lặp bên trong) cặp bởi @chux (tham khảo câu trả lời của ông), và so sánh với số lần lặp lại ước tính từ trên cao, ví dụ: n(1+ln(n))-ln(n). Rõ ràng là ước tính hài hòa gọn gàng với số lượng thực tế, xem các ô bên dưới hoặc this snippet for the actual numbers.

---

Cuối cùng lưu ý rằng nếu chúng ta để cho n->∞ trong tổng trên 1/i trên, hàng loạt kết quả là infinite harmonic series, đó là, một cách tò mò đủ, khác nhau. Các bằng chứng cho sau này làm cho việc sử dụng thực tế là trong vô hạn tổng số các điều khoản khác không tự nhiên là vô hạn riêng của mình. Tuy nhiên, trong thực tế, đối với đủ lớn nhưng không vô hạn n, ln(n) là xấp xỉ tổng hợp thích hợp và phân kỳ này không liên quan đến phân tích tiệm cận của chúng tôi tại đây.

---