Tóm Tắt
Big O Notation là gì ?
Big-O notation là ngôn ngữ chúng ta sử dụng để nói về thời gian một thuật toán thực thi (độ phức tạp về thời gian – time complexity) hoặc bao nhiêu bộ nhớ được sử dụng bởi một thuật toán (độ phức tạp không gian – space complexity). Big-O notation có thể thể hiện thời gian chạy tối ưu nhất, chậm nhất và trung bình của một thuật toán. Trong bài viế này chúng ta sẽ tập trung chủ yếu vào time complexity, tức độ phức tạp về thời gian.
Là một kỹ sư phần mềm, bạn sẽ thấy rằng hầu hết các cuộc thảo luận về Big-O đều tập trung vào thời gian chạy “giới hạn trên” của một thuật toán, thường được gọi là trường hợp xấu nhất. Một phần quan trọng cần lưu ý là “thời gian chạy” khi sử dụng Big-O notation không trực tiếp tương đương với thời gian như chúng ta biết (ví dụ: giây, mili giây, micro giây, v.v.). Phân tích thời gian chạy không tính đến những thứ nhất định, chẳng hạn như bộ xử lý, ngôn ngữ hoặc môi trường thời gian chạy. Thay vào đó, chúng ta có thể coi thời gian là số phép tính hoặc số bước cần thực hiện để hoàn thành một bài toán cỡ n. Nói cách khác, ký hiệu Big-O là một cách để theo dõi thời gian chạy (runtime) phát triển nhanh như thế nào so với kích thước của đầu vào (input).
Khi chúng ta nghĩ về trường hợp xấu nhất, câu hỏi trở thành – những phép tính / bước nào có thể xảy ra nhất đối với đầu vào có kích thước n?
Trong biểu đồ trên, trục Y được gắn nhãn Operations và trục X được gắn nhãn là Elements. Elements đề cập đến số lượng nguồn vào trong khi Operations đề cập đến số lượng phép tính được sử dụng để giải quyết và xử lý số lượng nguồn vào nói trên. Có bảy mức độ phức tạp về thời hạn khác nhau với tên gọi riêng và tất cả chúng ta sẽ đi qua các khái niệm này .
Những mức độ phức tạp của Big O
O ( 1 ) → Thời gian là hằng số
O (1) có nghĩa là cần một thời gian không đổi để chạy một thuật toán, bất kể kích thước của đầu vào.
Bookmark ( lưu lại trang ) là một ví dụ tuyệt vời về thời hạn không đổi sẽ diễn ra như thế nào trong quốc tế thực. Đánh dấu trang được cho phép người đọc tìm thấy trang ở đầu cuối mà bạn đã đọc một cách nhanh gọn và hiệu suất cao. Không khác nhau nếu bạn đang đọc một cuốn sách có 30 trang hay một cuốn sách có 1000 trang. Miễn là bạn đang sử dụng bookmark, bạn sẽ tìm thấy trang sau cuối đó trong một bước duy nhất .Trong lập trình, rất nhiều thao tác là hằng số. Dưới đây là 1 số ít ví dụ :
- phép toán
- truy cập một mảng thông qua chỉ mục
- truy cập hàm băm thông qua khóa
- push và pop trên một ngăn xếp
- chèn và xóa khỏi hàng đợi
- trả về một giá trị từ một hàm
Hãy xem findFirstIndex, được liệt kê bên dưới. Truyền smallCollection hoặc giganticCollection sẽ tạo ra cùng một thời gian chạy của O (1) khi truy cập chỉ mục 0. Trả về của firstIndex cũng là một hoạt động theo thời gian không đổi. Bất kể kích thước của n, cả hai hoạt động này sẽ mất một khoảng thời gian không đổi.
O ( n ) → thời hạn tuyến tính
O (n) có nghĩa là thời gian chạy tăng cùng tốc độ với đầu vào.
Hành động đọc sách là một ví dụ về thời hạn tuyến tính ( linear ) sẽ diễn ra như thế nào trong quốc tế thực. Giả sử rằng ta mất đúng 1 phút để đọc một trang của một cuốn sách in khổ lớn. Cho rằng, một cuốn sách có 30 trang, tôi sẽ mất 30 phút để đọc. Tương tự như vậy, một cuốn sách có 1000 trang = 1000 phút đọc. Chúng ta hoàn toàn có thể không buộc mình phải hoàn thành xong những cuốn sách không hay – thế cho nên, luôn có năng lực tôi sẽ không đọc hết cuốn sách 1.000 trang đó. Tuy nhiên, trước khi bắt đầu đọc, tôi hoàn toàn có thể biết rằng thời hạn đọc trong trường hợp tệ nhất của tôi là 1000 phút cho một cuốn sách 1000 trang .
Trong lập trình, một trong những phép toán thời gian tuyến tính phổ biến nhất là duyệt qua một mảng. Trong JavaScript, các phương thức như forEach, map và Reduce chạy xuyên suốt toàn bộ bộ sưu tập dữ liệu, từ đầu đến cuối.
Hãy xem hàm printAllValues của chúng ta bên dưới. Số phép toán mà nó sẽ thực hiện để lặp qua n liên quan trực tiếp đến kích thước của n. Nói chung (nhưng không phải lúc nào cũng vậy), việc nhìn thấy một vòng lặp là một dấu hiệu cho thấy đoạn mã cụ thể mà bạn đang kiểm tra có thời gian chạy là O (n).
Nhưng những gì về phương pháp tìm thấy? Vì nó không phải lúc nào cũng chạy qua toàn bộ collection, nó có thực sự là tuyến tính không? Trong ví dụ dưới đây, giá trị đầu tiên nhỏ hơn 3 nằm ở chỉ mục 0 của tập hợp. Tại sao đây không phải là thời gian cố định?
Hãy nhớ rằng – vì tất cả chúng ta đang tìm kiếm trường hợp xấu nhất, tất cả chúng ta phải giả định rằng nguồn vào sẽ không phải là lý tưởng và thành phần hoặc giá trị mà tất cả chúng ta tìm kiếm hoàn toàn có thể là giá trị ở đầu cuối trong mảng. Trong trường hợp thứ hai ( bên dưới ), bạn sẽ thấy điều đó. Tìm số nhỏ hơn ba, trong trường hợp ít lý tưởng nhất, sẽ nhu yếu lặp lại hàng loạt mảng .
O ( n² ) → Thời gian bậc hai
O (n²) có nghĩa là phép tính chạy theo thời gian bậc hai (quadratic), là kích thước bình phương của dữ liệu đầu vào.
Trong lập trình, nhiều thuật toán sắp xếp cơ bản hơn có thời hạn chạy trong trường hợp xấu nhất là O ( n² ) :
- Bubble Sort
- Insertion Sort
- Selection Sort
Hãy xem hàm countOperations bên dưới. Ở đây chúng ta có hai vòng lặp lồng nhau đang tăng biến hoạt động sau mỗi lần lặp. Nếu n là smallCollection, chúng ta sẽ kết thúc với số lượng 16 phép toán. Khá nhỏ. Nhưng nếu n là giganticCollection của chúng ta thì sao? Một tỷ lần một tỷ là ngàn tỷ tỷ tỷ (1030) – hoặc 1.000.000.000.000.000.000.000. Rất, rất nhiều. Ngay cả một mảng có ít nhất 1.000 phần tử cũng sẽ tạo ra một triệu phép toán.
Nói chung (nhưng không phải lúc nào cũng vậy), việc nhìn thấy hai vòng lặp lồng nhau thường là một tín hiệu cho thấy đoạn code bạn đang xem có thời gian chạy là O (n²). Tương tự như vậy – ba vòng lặp lồng nhau sẽ cho biết thời gian chạy là O (n³).
O ( log n ) → Thời gian logarit ( Logarithmic Time )
O (log n) có nghĩa là thời gian chạy tăng tương ứng với logarit của kích thước đầu vào, có nghĩa là thời gian chạy hầu như không tăng khi bạn tăng đầu vào theo cấp số nhân.
Tìm một từ trong từ điển vật lý bằng cách giảm 50% size mẫu là một ví dụ tuyệt vời về cách hoạt động giải trí của thời hạn logarit trong quốc tế thực. Ví dụ : khi tìm từ “ senior ”, bạn hoàn toàn có thể mở từ điển một cách đúng chuẩn ở giữa – tại thời gian đó bạn hoàn toàn có thể xác lập xem những từ khởi đầu bằng “ s ” đứng trước hay sau những từ mà ban hiện đang xem. Khi bạn xác lập rằng “ s ” nằm ở nửa sau của cuốn sách, bạn hoàn toàn có thể vô hiệu toàn bộ các trang trong nửa đầu. Sau đó bạn lặp lại quy trình tương tự như. Bằng cách làm theo thuật toán này đến cùng, bạn sẽ cắt giảm 1/2 số trang tôi phải tìm kiếm mỗi lần cho đến khi tôi tìm thấy từ đó .Trong lập trình, hành vi tìm kiếm trong từ điển vật lý này là một ví dụ của thao tác tìm kiếm nhị phân – đây là ví dụ nổi bật nhất được sử dụng khi luận bàn về thời hạn chạy của lôgarit ( logarithmic runtimes )
Hãy xem phiên bản sửa đổi của hàm countOperations của. Lưu ý rằng n bây giờ là một số: n có thể là một đầu vào (số) hoặc kích thước của một đầu vào (độ dài của một mảng).
Trong ví dụ của chúng tôi ở trên, chúng ta kết thúc với 11 phép toán nếu n = 2000. Nếu n = 4.000, chúng tôi kết thúc với 12 phép toán. Mỗi khi chúng ta tăng gấp đôi số lượng n, số lượng phép toán chỉ tăng thêm 1. Các thuật toán chạy theo thời gian logarit có ý nghĩa lớn khi nói đến các đầu vào lớn hơn. Sử dụng ví dụ trẹn, O (log (7)) sẽ trả về ba phép toán. Một O (log (1000000)) sẽ chỉ trả về 20 phép toán.
O ( n log n ) → Thời gian chạy tuyến tính với logarit
O(n log n), thường bị nhầm lẫn với O (log n), có nghĩa là thời gian chạy của một thuật toán là tuyến tính, là sự kết hợp của độ phức tạp tuyến tính và logarit.
Các thuật toán sắp xếp sử dụng kế hoạch chia để trị có độ phức tạp dạng linearithmic này, ví dụ điển hình như sau :
- merge sort
- timsort
- heapsort
Khi xem xét độ phức tạp thời hạn, O ( n log n ) nằm giữa O ( n2 ) và O ( n ) .
Tính toán độ phức tạp của thuật toán
Cho đến lúc này, tất cả chúng ta chỉ tập trung chuyên sâu vào việc nói về Big-O bằng cách cô lập một vài dòng mã tại một thời gian. Làm cách nào để thống kê giám sát Big-O nếu tất cả chúng ta đang giải quyết và xử lý một thuật toán có nhiều phần ?
Bỏ các hằng số ( constants )
Hãy bắt đầu với logEverythingTwice.
Vì Big-O chăm sóc đến việc thời hạn chạy của tất cả chúng ta tăng trưởng nhanh như thế nào, nên quy tắc tiên phong bạn muốn nhớ là bỏ bất kể hằng số nào khi bạn nghiên cứu và phân tích một thuật toán .
Trong ví dụ trên, tất cả chúng ta có hai vòng lặp riêng không liên quan gì đến nhau đang lặp qua độ dài của một mảng ( tuyến tính ). Mỗi vòng lặp ghi lại một mục trong collection ( hằng số ). Vì tất cả chúng ta không chăm sóc đến các phép tính chạy trong thời hạn không đổi ( chúng tạo ra sự độc lạ nhỏ trong ước tính tổng thể và toàn diện ), tất cả chúng ta sẽ chỉ tính đến hai vòng lặp và cộng chúng lại với nhau và cho tất cả chúng ta tác dụng O ( 2 n ). Vì số hai cũng là một hằng số trong trường hợp này, tất cả chúng ta vô hiệu nó và gọi nó là O ( n ) .
Nhưng điều gì sẽ xảy ra nếu những vòng lặp này được lồng vào nhau?
Với việc lồng các vòng lặp này, chúng ta không còn ghi lại các items[i] hai lần nữa – mà là năm lần! Trong trường hợp này, chúng ta nhân O (n) * O (n) thay vì cộng số lần chạy với nhau. Chúng ta làm điều này bởi vì việc thực thi nhật log của chúng ta phụ thuộc vào việc lặp lại toàn bộ vòng lặp thứ hai (ghi lại i năm lần) trước khi chúng ta có thể tăng i và chuyển sang index tiếp theo thông qua vòng lặp đầu tiên. Đây là những gì log của chúng ta kết thúc trả về:
1
1
1
1
1
2
2
2
2
2
3
3
….
Cũng giống như ví dụ tiên phong, chúng tôi vẫn muốn vô hiệu các hằng số khỏi các logs. Cuối cùng, O ( n * n ) cho tất cả chúng ta O ( n² ) .Bài học ở đây là bạn luôn tránh các vòng lặp lồng nhau do tác động ảnh hưởng của hiệu suất. Bạn chắc như đinh sẽ gặp phải những trường hợp phải dùng giải pháp như vậy ( tập tài liệu nhỏ, thao tác với mảng đa chiều, v.v. ). Tuy nhiên, bạn nên biết rằng hoàn toàn có thể có những tác động ảnh hưởng về hiệu suất, tùy thuộc vào những gì bạn đang làm .
Bỏ các lao lý không chiếm lợi thế
Hãy xem một ví dụ khác .
Sau khi loại bỏ các hằng số trong printMultiplesThenSum, chúng ta có thể thấy rằng Big-O notation cho hàm này sẽ là O (n² + n). Vì Big-O cũng không liên quan đến các số hạng không chiếm ưu thế, chúng ta bỏ n (thắng bậc hai vì nó tệ hơn thời gian tuyến tính). Loại bỏ các thuật ngữ không chiếm ưu thế là quy tắc thứ hai cần tuân theo khi phân tích thời gian chạy của một thuật toán. Cuối cùng, O (n² + n) cho chúng ta O (n²).
Tại sao bạn cần biết về độ phức tạp của thuật toán ?
Sau khi đã khám phá các khái niệm trên, bạn dã biết tại sao các công ty lại hỏi bạn về Big-O notation trong một cuộc phỏng vấn ?Câu vấn đáp là việc điều tra và nghiên cứu độ phức tạp của thuật toán giúp bạn chớp lấy được khái niệm rất quan trọng về hiệu suất cao trong code của bạn. Khi bạn thao tác với các tập dữ liệu khổng lồ, bạn sẽ hiểu rõ nơi nào có năng lực gây ra ùn tắc lớn và nơi nào cần quan tâm nhiều hơn để có được những nâng cấp cải tiến lớn nhất. Đây còn được gọi là nghiên cứu và phân tích độ nhạy ( sensitivity analysis ), và là một phần quan trọng trong việc xử lý yếu tố và viết ứng dụng một cách tối ưu nhất .Vì vậy, nếu bạn đang sẵn sàng chuẩn bị cho cuộc phỏng vấn về lập trình, thì việc nâng cao kiến thức về các khái niệm như Big O notation và các chủ đề khoa học máy tính khác sẽ giúp bạn tự tin hơn. Bạn sẽ được trang bị tốt hơn để biểu lộ khả của mình và gây ấn tượng so với nhà tuyển dụng .Xem thêm các bài về phỏng vấn lập trình trên ITguruTài liệu cho bài viết này :Bạn nhìn nhận bài viết thế nào ?
Average rating 4.6 / 5. Vote count : 5No votes so far ! Be the first to rate this post .
Source: https://final-blade.com
Category : Kiến thức Internet
