Big O, độ phức tạp của việc tổng hợp một chuỗi số n là bao nhiêu?

Question

Tôi luôn nghĩ sự phức tạp của:

1 + 2 + 3 + ... + n là O (n) và tổng hai ma trận n bằng n sẽ là O (n^2).

Nhưng hôm nay tôi đọc từ sách giáo khoa, "theo công thức tính tổng n số nguyên đầu tiên, đây là n (n + 1)/2" và sau đó: (1/2) n^2 + (1/2) n, và do đó O (n^2).

Tôi thiếu gì ở đây?

Answer 1

Có thể sử dụng big O notation để xác định tốc độ tăng trưởng mọi chức năng.

Trong trường hợp này, có vẻ như cuốn sách không nói về độ phức tạp của thời gian tính toán giá trị, mà còn về bản thân giá trị. Và n(n+1)/2 là O(n^2).

Answer 2

Bạn có công thức không phụ thuộc vào số lượng được thêm vào, vì vậy đây là một thuật toán hằng số không đổi hoặc O (1).

Nếu bạn thêm từng số một tại một thời điểm, thì đó thực sự là O (n). Công thức là một phím tắt; đó là một thuật toán khác, hiệu quả hơn. Phím tắt hoạt động khi các số được thêm vào là tất cả 1 .. n. Nếu bạn có một dãy số không tiếp giáp, thì công thức phím tắt sẽ không hoạt động và bạn sẽ phải quay lại thuật toán từng người một.

Không có điều nào trong số này áp dụng cho ma trận số. Để thêm hai ma trận, nó vẫn là O (n^2) bởi vì bạn đang thêm n^2 cặp riêng biệt của các số để có được một ma trận của n^2 kết quả.

Answer 3

n (n + 1)/2 là cách nhanh chóng để tổng hợp chuỗi liên tiếp của số nguyên N (bắt đầu từ 1). Tôi nghĩ rằng bạn đang bối rối một thuật toán với ký hiệu lớn-oh!

Nếu bạn nghĩ về nó như một chức năng thì lớn-oh phức tạp của chức năng này là O (1):

 
public int sum_of_first_n_integers(int n) { 
    return (n * (n+1))/2; 
} 

Việc thực hiện ngây thơ sẽ phải lớn-oh phức tạp của O (n).

public int sum_of_first_n_integers(int n) { 
    int sum = 0; 
    for (int i = 1; i <= n; i++) { 
    sum += n; 
    } 
    return sum; 
} 

Ngay cả khi chỉ xem từng ô của một ma trận n-by-n là O (n^2), vì ma trận có n^2 ô.

Answer 4

Có sự khác biệt giữa tổng N số nguyên tùy ý và tổng N là tất cả trong một hàng. Đối với 1 + 2 + 3 + 4 + ... + N, bạn có thể tận dụng thực tế là chúng có thể được chia thành các cặp với một số tiền chung, ví dụ: 1 + N = 2+ (N-1) = 3+ (N-2) = ... = N + 1. Vì vậy, đó là N + 1, N/2 lần. (Nếu có một số lẻ, một trong số đó sẽ được bỏ ghép, nhưng với một chút nỗ lực bạn có thể thấy rằng cùng một công thức giữ trong trường hợp đó.)

Đó không phải là O (N^2). Nó chỉ là một công thức mà sử dụng N^2, thực sự là O (1). O (N^2) có nghĩa là (gần) rằng số bước để tính toán nó phát triển như N^2, đối với N. lớn. Trong trường hợp này, số lượng các bước là như nhau bất kể N.

Answer 5

Có thực sự không phải là một vấn đề phức tạp, mà là sự phức tạp của một thuật toán.

Trong trường hợp của bạn, nếu bạn chọn lặp qua tất cả các số, độ phức tạp thực tế là O(n).

Nhưng đó không phải là thuật toán hiệu quả nhất. Một cách hiệu quả hơn là áp dụng công thức - n*(n+1)/2, là hằng số và do đó độ phức tạp là O(1).

Answer 6

Bạn khó hiểu về độ phức tạp của thời gian chạy và kích thước (độ phức tạp) của kết quả .

Các thời gian chạy của tổng hợp, một sau khi khác, n số liên tiếp đầu tiên thực sự O ( n) là.

Nhưng sự phức tạp của kết quả, đó là kích thước của “tổng 1-n” = n ( n-1)/2 là O ( n^2).

---

Nhưng đối với số tùy tiện lớn này là đơn giản từ cách thêm một số lượng lớn mất nhiều thời gian hơn so với cách thêm số lượng nhỏ. Đối với một phân tích thời gian chạy chính xác, bạn thực sự phải xem xét kích thước của kết quả. Tuy nhiên, điều này thường không liên quan đến lập trình, thậm chí không hoàn toàn trong khoa học máy tính lý thuyết. Trong cả hai tên miền, số tổng hợp thường được coi là hoạt động O (1) trừ khi được miền yêu cầu một cách rõ ràng (ví dụ: khi triển khai hoạt động cho thư viện bignum).

Answer 7

câu trả lời của tổng số chuỗi n tự nhiên có thể được tìm thấy bằng hai cách. cách đầu tiên là bằng cách thêm tất cả các số trong vòng lặp. trong thuật toán trường hợp này là tuyến tính và mã sẽ như thế này

int sum = 0; 
    for (int i = 1; i <= n; i++) { 
    sum += n; 
    } 
return sum; 

tương tự như 1 + 2 + 3 + 4 + ...... + n. trong trường hợp này, độ phức tạp của thuật toán được tính bằng số lần hoạt động bổ sung được thực hiện là O (n).

cách thứ hai để tìm câu trả lời tổng của chuỗi số tự nhiên n là công thức direst n * (n + 1)/2. công thức này sử dụng phép nhân thay vì lặp lại lặp đi lặp lại. phép toán nhân không có độ phức tạp về thời gian tuyến tính. có các thuật toán khác nhau có sẵn cho phép nhân có độ phức tạp thời gian khác nhau, từ O (N^1,45) đến O (N^2). do đó trong trường hợp phức tạp thời gian phép nhân phụ thuộc vào kiến ​​trúc của bộ vi xử lý. nhưng với mục đích phân tích thời gian phức tạp của phép nhân được coi là O (N^2). do đó khi sử dụng cách thứ hai để tìm tổng thì độ phức tạp của thời gian sẽ là O (N^2).

tại đây hoạt động nhân giống không giống như thao tác bổ sung. nếu ai có kiến ​​thức về chủ thể tổ chức máy tính thì anh ta có thể dễ dàng hiểu được hoạt động nội bộ của phép nhân và phép cộng. mạch nhân là phức tạp hơn so với mạch cộng và đòi hỏi thời gian cao hơn nhiều so với mạch cộng để tính toán kết quả. do đó, thời gian phức tạp của tổng của chuỗi không thể không đổi.

Answer 8

Vì vậy, tôi đoán là điều này thực sự là một tài liệu tham khảo để Cracking the Coding Interview, trong đó có đoạn này trên thực hiện StringBuffer:

Trên mỗi nối, một bản sao mới của chuỗi được tạo ra, và hai chuỗi được sao chép, ký tự theo ký tự. Lần lặp đầu tiên yêu cầu chúng tôi sao chép x ký tự. Lặp lại thứ hai yêu cầu sao chép 2x ký tự. Lần lặp thứ ba yêu cầu 3x và , v.v. Do đó tổng thời gian là O(x + 2x + ... + nx). Điều này làm giảm thành O(xn²). (Tại sao không phải là nó O(xnⁿ)? Bởi vì 1 + 2 + ... n bằng n(n+1)/2 hay, O(n²).)

Đối với bất cứ lý do Tôi thấy điều này một chút bối rối trên đầu tiên của tôi đọc qua, quá. Điều quan trọng cần xem là n nhân với số n hoặc nói cách khác là n² đang diễn ra và điều đó thống trị. Đây là lý do tại sao cuối cùng là O(xn²) chỉ là O(n²) - số x là loại cá trích màu đỏ.