BIG O NOTATION LÀ GÌ

Share:
Ký hiệu Big O – thực hiện toán học để đo lường kết quả thuật toán. Mọi bạn học cấu tạo dữ liệu và giải mã hay trong thiết kế chắc đông đảo nghe tới định nghĩa Big O rồi chứ nhỉ, ví dụ như như giải thuật tìm tìm này mất O(n) đơn vị để thực hiện,….

Bạn đang đọc: Big o notation là gì

Bạn đang xem: Big o notation là gì

Khái niệm Big O hoặc với tên thường gọi khác trong tiếng Việt là “độ phức hợp của thuật toán” là thuật ngữ thường dùng làm chỉ khoảng thời hạn tiêu hao nhằm chạy một thuật toán. Các lập trình viên thường áp dụng Big O như một phương tiện để đối chiếu mức độ công dụng của nhiều cách xử lý khác biệt cho cùng một vấn đề. Ký kết hiệu Big O cho phép họ tính toán thời gian chạy tồi tệ độc nhất của thuật toán hoặc mất bao lâu để thuật toán trả thành. Nói bí quyết khác, nó thông báo cho bọn họ về việc nó sẽ chậm lại bao nhiêu dựa trên kích thước đầu vào. Nó luôn luôn luôn giỏi để biết một thuật toán chạy nhanh như vậy nào bởi vì chúng ta luôn đạt được thời gian nhanh nhất một giải pháp hiệu quả. Rộng nữa, nó là một trong khái niệm quan trọng cần phải biết khi tiến hành các cuộc phỏng vấn mã hóa bởi nó thực sự cho biết thêm sự đọc biết của khách hàng về xử lý vấn đề và hiệu quả. Có rất nhiều thời gian chạy hoặc độ tinh vi thời gian mà Big O bao trùm, tuy nhiên trong phần này, mình sẽ tìm hiểu bao hàm bốn độ phức hợp thời gian chính.
*

Graph displays 4 time complexities to lớn visually understand runtimes

Thời gian chạy liên tục: “O (1)”

arr = def print_all(arr) puts "#arr" # prints out 3 puts "#arr" # prints out 1endprint_all(arr)Thời gian chạy của thủ tục này là hằng số hoặc O (1). Vì sao là mặc dầu mảng to đến đâu, số lượng thao tác bọn họ thực hiện tại không lúc nào thay đổi. Nó liên tục. Chúng ta chỉ in ra chỉ mục trước tiên và sản phẩm công nghệ hai của mảng từng lần.

Xem thêm: Gia Đình Ca Sĩ Trọng Tấn - Vợ Chồng Trọng Tấn Sống Kiểu Quê Trong Nhà Phố

Thời gian chạy tuyến tính: “O (n)”

arr = def print_all(arr) arr.each bởi vì |num| puts "#num" endendprint_all(arr)Thời gian chạy của thủ tục này là tuyến tính hoặc O (n). Như bạn cũng có thể thấy, bọn họ có một vòng lặp bên trong phương thức lần này tái diễn trên cục bộ mảng với in ra phần tử. Mặc dù nhiên, số lượng thao tác làm việc mà vòng lặp này triển khai sẽ nuốm đổi, bởi tùy thuộc vào con số phần tử bên phía trong mảng, vòng lặp vẫn phải tiến hành số lần lặp đúng đắn dựa trên size đầu vào. Một mảng có form size 5 đang chỉ mất 5 lần lặp trong khi một mảng có kích cỡ 10 sẽ mất 10 lần lặp, dài gấp đôi. Bởi vì vậy, khi kích cỡ đầu vào tăng, thời gian chạy cũng trở nên tăng.

Thời gian đuổi theo cấp số nhân: “O (n²)”

def print_all(arr) arr.each vì |letter1| arr.each bởi vì |letter2| puts "#letter1" + "#letter2" kết thúc endendprint_all() # prints out 9 pairsprint_all() # prints out 16 pairsThời gian chạy của cách làm này là hàm nón hoặc O (n²). Trong trường phù hợp này, chúng ta có một vòng lặp bên phía trong một vòng lặp. Tùy nằm trong vào kích thước của mảng, vòng lặp bên ngoài sẽ thực hiện lần lặp trước tiên và tiếp đến vòng lặp bên phía trong sẽ lặp lại qua mảngENTIREtrước khi trở lại vòng lặp lắp thêm hai của vòng lặp bên phía ngoài và nó vẫn tiếp tục cho tới khi vòng lặp bên phía ngoài đạt được sự dứt của mảng. Thời hạn chạy này khôn xiết không hiệu quả. Khi bạn có một mảng lớn, tốt nhất là kị sử dụng các thuật toán sử dụng thời hạn chạy này vị sẽ mất rất nhiều thời gian. Vào phương thức, kích thước mảng 3 đã in ra 9 cặp và size mảng 4 đã in ra 16 cặp: vòng lặp cần bình phương mốc giới hạn lặp dựa trên kích thước đầu vào, bởi vì đó lý do nó gọi là thời gian chạy theo hàm mũ. Một cái nào đấy với kích thước mảng là 100 đang mất 10.000 lần lặp. Và không người nào muốn điều đó.Mình sẽ không những ra một phương pháp cho bài toán này bởi vì nó tốt hơn để phân tích và lý giải nó. Thời gian chạy logarit là một thời gian chạy cực kỳ hiệu quả. Nếu một mảng có kích cỡ 4000 phần tử, rất có thể sẽ chỉ mất 12 thao tác để kiếm tìm thấy phần nhiều gì ai đang tìm tìm trái ngược cùng với việc lặp lại trên cục bộ mảng. Một ví dụ luôn có thời gian chạy logarit là Binary search (cấu trúc dữ liệu). Tìm kiếm nhị phân hoạt động như rứa này: đưa sử các bạn nói rằng bạn đã giới thiệu một mảng được sắp xếp theo lắp thêm tự số hoặc chữ cái. Trong trường hòa hợp này, bọn họ sẽ thực hiện một mảng theo thiết bị tự số.Mục tiêu của chúng ta là tìm một số trong những nhất định vào mảng này, đưa sử 9. Chà, dự đoán thứ nhất của bạn chắc rằng là tạo ra một vòng lặp với chỉ bước đầu từ đầu của mảng để đến đó, nhưng mà sẽ mất 9 lần lặp để bạn đã có được 9, đang chỉ khiến cho nó một thời hạn chạy con đường tính. Nếu khách hàng có một mảng được đặt hàng với 1..1000 và bạn muốn tìm 999, bạn sẽ phải tái diễn theo nghĩa black 999 lần để có được số. Tuy nhiên tất nhiên, kiếm tìm kiếm nhị phân tạo cho điều này dễ dãi hơn bởi cách ban đầu ở giữa mảng. Tất cả hai giá trị trung bình ở đây nhưng chúng ta sẽ lựa chọn 5 và bước đầu từ đó. Sau đó, họ nhìn vào bên trái và bên cần của 5. Là quý hiếm 9, mà chúng ta đang tra cứu kiếm, ở phía bên trái hoặc bên nên của 5? 9 làm việc bên đề xuất của 5, vì vậy bọn họ bỏ qua phía bên trái của 5 và bước đầu ở giữa nửa bên đề xuất của 5.Bây giờ chúng ta tìm kiếm thông qua một phần rút ngắn của mảng. Và họ chỉ lặp lại quá trình tương tự! Hãy quan sát vào giữa của mảng này, bọn họ sẽ chọn 8 cho mảng này. Sau đó, chúng ta nhìn sang phía bên trái và bên đề nghị của 8. 9 ở bên đề nghị của 8, vì chưng vậy bọn họ hoàn toàn làm lơ phía phía trái của 8 và hiện giờ chúng ta tra cứu kiếm thông sang 1 mảng thậm chí còn còn rút ngắn hơn.Một lần nữa, chúng ta ban đầu ở giữa mảng, là 9. Tuy thế hãy quan sát xem, thân của mảng ban đầu bằng 9, quý hiếm mà họ đang tra cứu kiếm! vị vậy, bây giờ bạn có thể lấy quý hiếm đó một phương pháp dễ dàng. Điều này thực sự mất 3 thao tác khi mảng có kích thước đầu vào là 10.Biết được thời hạn chạy của các thuật toán và cách nâng cao chúng là vì sao tại sao Big O Notation tồn tại. Trở nên tân tiến các thuật toán hiệu quả hơn dẫn đến thời hạn chạy cấp tốc hơn và ít mã rộng (độ phức tạp không gian). (Mình chỉ trải qua khía cạnh tinh vi về thời hạn của Big O, nhưng cũng có thể có sự phức tạp về không khí mà mình hoàn toàn có thể làm trong một blog tương lai.) và như tôi đã nói trước đây, điều này không bao gồm mọi vật dụng trong sự phức hợp về thời hạn của Big O khi tôi chỉ đề cập đến những nguyên tắc cơ phiên bản và thông dụng nhất vì chưng vậy đừng lấy phần đa thứ tại đây vì "Đây là về Big O, bây giờ tôi vẫn sẵn sàng cho những cuộc vấn đáp về mã hóa"! Chỉ cần chắc chắn rằng để thực hiện một vài nghiên cứu vãn về thời hạn chạy khác và làm ráng nào các thuật toán khác minh họa điều đó.

Bài viết liên quan