Nơi để tìm thấy những gì O (n^2) và O (n) vv có nghĩa là?

Question

Tôi đã nhận thấy câu trả lời trên tràn ngăn xếp sử dụng các thuật ngữ như thế này, nhưng tôi không biết ý nghĩa của chúng. Họ được gọi là gì và có một nguồn tài nguyên tốt có thể giải thích chúng một cách đơn giản không?

Answer 1

Đó ký hiệu được gọi là Big O notation, và được sử dụng như một kí hiệu để thể hiện độ phức tạp thuật toán (về cơ bản bao lâu một algorithim nhất định sẽ làm để chạy như kích thước đầu vào (n) phát triển)

Nói chung, bạn sẽ chạy thành các loại chủ yếu sau đây của algorithims:

1. O (1) - liên tục - chiều dài của thời gian đó algorithim này cần để hoàn thành không phụ thuộc vào số lượng các mục mà algorithim có để xử lý.
2. O (log n) - lôgarít - Khoảng thời gian mà thuật toán này cần để hoàn thành phụ thuộc vào số lượng mục mà thuật toán phải xử lý. Khi kích thước đầu vào trở nên lớn hơn, cần ít thời gian hơn cho mỗi đầu vào mới.
3. O (n) - Tuyến tính - Khoảng thời gian mà thuật toán này cần để hoàn thành phụ thuộc trực tiếp vào số lượng mục mà thuật toán phải xử lý. Khi kích thước đầu vào tăng lên, thời gian cần tăng theo số lượng bằng nhau.
4. O (n^2) - Đa thức - Khi kích thước đầu vào tăng, thời gian cần để xử lý đầu vào tăng lên bởi số lượng lớn hơn và lớn hơn - có nghĩa là kích thước đầu vào lớn trở nên khó giải quyết.
5. O (2^n) - Số mũ - Các loại vấn đề phức tạp nhất. Thời gian để xử lý tăng dựa trên kích thước đầu vào đến một mức độ cực đoan.

Nói chung, bạn có thể nhận được đánh giá sơ bộ về độ phức tạp của thuật toán bằng cách xem cách nó được sử dụng. Ví dụ, nhìn vào phương pháp sau đây:

function sum(int[] x) { 
    int sum = 0; 
    for (int i = 0; i < x.length; i++) { 
     sum += x[i]; 
    } 
    return sum; 
} 

Có một vài điều mà phải được thực hiện ở đây:

• Khởi tạo một biến gọi là tổng
• khởi tạo một biến gọi là i
• cho mỗi lần lặp của i: Thêm x [i] để tính tổng, thêm 1 vào i, kiểm tra nếu i nhỏ hơn x.chiều dài
• Return tổng

Có một vài hoạt động mà chạy trong thời gian liên tục ở đây (hai đầu tiên và cuối cùng), vì kích thước của x sẽ không ảnh hưởng đến bao lâu họ có được để chạy. Đồng thời, có một số hoạt động chạy trong thời gian tuyến tính (vì chúng được chạy một lần cho mỗi mục nhập trong x). Với Big O ký hiệu, các algorithim được đơn giản hóa đến phức tạp nhất, vì vậy tổng algorithim này sẽ chạy trong O (n)

Answer 2

Đọc khoảng Computational Complexity trước tiên, sau đó thử một số sách về các thuật toán như Introduction to Algorithms.

Từ trang Wikipedia:

Big O ký hiệu đặc trưng chức năng theo tốc độ tăng trưởng của họ

Nếu bạn không sẽ không để khoan sâu vào chi tiết, bạn có thể rất thường xuyên xấp xỉ thuật toán phức tạp bằng cách mã hóa mã của nó:

void simpleFunction(arg); // O(1) - if number of function instructions is constant and don't depend on number of input size 

for (int i=0;i<n;i++) {simpleFunction(element[i]);} // O(n) 

for (int i=0;i<n;i++) { // this one runs O(n^2) 
    for (int j=0;j<n;j++) { 
     simpleFunction(element[i]); 
    } 
} 

for (int i=0;i<n;i*=2) { // O(lgn) 
    simpleFunction(element[i]); 
} 

Đôi khi nó không đơn giản để ước tính hàm/thuật toán phức tạp ký hiệu O lớn trong suc h trường hợp amortized analysis được sử dụng. Mã trên chỉ nên phân phối nhanh hơn.

Answer 3

này được gọi là Big O notation và được sử dụng để định lượng mức độ phức tạp của thuật toán.

O (1) có nghĩa là thuật toán mất một thời gian liên tục bất kể có bao nhiêu dữ liệu để xử lý.

O (n) có nghĩa là tốc độ thuật toán tăng theo cách tuyến tính với lượng dữ liệu.

và cứ thế ...

Vì vậy, sức mạnh của n thấp hơn trong ký hiệu O, thuật toán của bạn càng tốt để giải quyết vấn đề. Trường hợp tốt nhất là O (1) (n = 0). Nhưng có một sự phức tạp vốn có trong nhiều vấn đề để bạn sẽ không tìm thấy một thuật toán lý tưởng như vậy trong gần như tất cả các trường hợp.

Answer 4

Câu trả lời là tốt cho đến nay. Thuật ngữ chính để tìm kiếm trên web là "Ký hiệu Big O".

Ý tưởng cơ bản đằng sau phép tính của "someformula là O (someterm)" là, khi biến của bạn đi đến vô cùng, "someterm" là một phần của công thức thống trị.

Ví dụ: giả sử bạn có 0.05*x^3 + 300*x^2 + 200000000*x + 10. Đối với các kích thước rất thấp x (x == 1 hoặc x == 2), thì 200000000*x sẽ là phần lớn nhất. Tại thời điểm đó một âm mưu của công thức sẽ trông tuyến tính. Khi bạn đi cùng, tại một số điểm, phần 300*x^2 sẽ lớn hơn. Tuy nhiên, nếu bạn tiếp tục làm x thậm chí lớn hơn, lớn như bạn quan tâm, phần 0.05*x^3 sẽ là lớn nhất, và cuối cùng sẽ hoàn toàn vượt qua các phần khác của công thức. Đó là nơi nó trở nên rõ ràng từ một đồ thị mà bạn đang xem xét một chức năng khối. Vì vậy, chúng tôi sẽ nói rằng công thức là O(x^3).