Đã có lúc không gì khiến tôi sợ hãi hơn khi nghe câu hỏi, "Ký hiệu Big-O cho điều đó là gì?" Tôi nhớ lại chủ đề ở trường, nhưng vì nó liên quan đến toán học (vốn chưa bao giờ là môn học mạnh nhất của tôi) nên tôi đã bôi đen nó.
Tuy nhiên, khi sự nghiệp của tôi phát triển, tôi thấy mình:
- Nhìn vào biểu đồ hiệu suất
- Đang cố gắng gỡ lỗi các truy vấn chậm
- Được hỏi liệu tôi đã xem xét cách mã của mình sẽ giữ như thế nào khi tải tăng lên
Khi tôi quyết định đã đến lúc quay lại (hiểu chưa?) Để học Big-O, tôi đã rất ngạc nhiên về sự đơn giản ở mức độ cao của nó. Tôi đang chia sẻ những gì tôi học được trong bài viết này để bạn, các kỹ sư đồng nghiệp của tôi, không chỉ có thể vượt qua các cuộc phỏng vấn với màu sắc bay bổng mà còn xây dựng các hệ thống hiệu quả, có thể mở rộng.
Tôi hứa, Big-O không đáng sợ như nó có vẻ. Sau khi tải xuống, bạn có thể xem xét một thuật toán và dễ dàng phân biệt hiệu quả của nó mà không cần phải chạy một công cụ lập hồ sơ!
Ký hiệu Big-O là gì?
Ký hiệu Big-O là một cách ưa thích để nói, "Này, trường hợp xấu nhất cho thuật toán này là gì?" Bạn có thể đã thấy một hàm được mô tả là O (n) hoặc O (1). Điều này có nghĩa là:
- O (n) - Thời gian chạy trong trường hợp xấu nhất tăng tuyến tính khi kích thước đầu vào (n) tăng lên
- O (1) - Thời gian chạy trong trường hợp xấu nhất là không đổi đối với bất kỳ đầu vào kích thước nào
... và để thực sự hiểu điều này có nghĩa là gì, chúng ta cần tìm hiểu về không có triệu chứng
Không có dấu hiệu?
Hãy quay trở lại đại số ở trường trung học, xóa bỏ cuốn sách giáo khoa của chúng tôi và mở nó ra các chương về giới hạn và không triệu chứng.
- Phân tích giới hạn: xem điều gì xảy ra với một hàm khi nó tiếp cận một số giá trị
- Phân tích tiệm cận: xem điều gì sẽ xảy ra khi f (x) tiến đến vô cực
Ví dụ, giả sử chúng ta vẽ đồ thị hàm f (x) =x ^ 2 + 4x.
Chúng tôi có thể thực hiện các phân tích sau:- Phân tích giới hạn: Khi x tăng, f (x) tiến tới vô cùng, vì vậy chúng ta có thể nói rằng giới hạn của f (x) =x ^ 2 + 4x khi x tiến tới vô cùng là vô cùng. - Phân tích tiệm cận: Khi x trở nên rất lớn, số hạng 4x trở nên không đáng kể so với số hạng x ^ 2. Vì vậy, chúng ta có thể nói rằng f (x) =x ^ 2 + 4x trở nên gần như tương đương với f (x) =x ^ 2 cho các giá trị của x tiến tới vô cùng.
Để hiểu cách chúng ta có thể nói rằng một phần của hàm trở nên "không đáng kể", hãy xem xét điều gì sẽ xảy ra khi bạn cắm các số khác nhau vào hàm ban đầu. Ví dụ, khi x =1, hàm trả về 1 + 4 (bằng 5). Tuy nhiên, khi x =2.000, hàm trả về 4.000.000 + 8.000 (tương đương với 4.008.000) - số hạng x ^ 2 đóng góp nhiều hơn vào tổng số so với 4x.
Ký hiệu Big-O là một cách mô tả thời gian chạy của thuật toán thay đổi như thế nào khi kích thước của đầu vào thay đổi.
Điều gì xác định thời gian chạy của một thuật toán?
Nếu tôi hỏi bạn sẽ mất bao lâu để tìm một cái kim trong đống cỏ khô, tôi tưởng tượng bạn sẽ muốn biết bao nhiêu cỏ khô trong đống cỏ khô. Nếu tôi trả lời "10 cái", tôi cá rằng bạn sẽ khá tự tin rằng mình có thể tìm thấy cây kim trong vòng một hoặc hai phút, nhưng nếu tôi nói "1.000 cái", có lẽ bạn sẽ không hào hứng bằng.
Có một thông tin khác mà bạn nên biết. Mất bao nhiêu thời gian để tìm kiếm mỗi đống cỏ khô được thêm vào? Và điều gì sẽ xảy ra khi lượng cỏ khô tiến đến vô cùng?
Điều này rất giống với ví dụ về phân tích tiệm cận ở trên. Hãy xem thêm một ví dụ nữa để đảm bảo rằng tất cả chúng ta đã hiểu rõ điều này. Xét hàm f (x) =5x ^ 2 + 100x + 50. Chúng ta có thể vẽ đồ thị riêng biệt hai phần của hàm này:
Cũng giống như ví dụ trước, số hạng 5x ^ 2 cuối cùng trở nên lớn hơn số hạng 100x + 50, vì vậy chúng ta có thể loại bỏ chúng và nói rằng thời gian chạy của f (x) =5x ^ 2 + 100x + 50 phát triển thành x ^ 2.
Tất nhiên, điều đáng nói là có những yếu tố khác ảnh hưởng đến thời gian chạy, chẳng hạn như tốc độ của máy tính thực đang chạy chương trình và ngôn ngữ được sử dụng.
Tìm Big-O cho tìm kiếm tuyến tính
Hãy thực hiện phân tích Big-O của thuật toán tìm kiếm tuyến tính. Tìm kiếm tuyến tính bắt đầu ở đầu tập dữ liệu và duyệt qua cho đến khi tìm thấy phần tử đích.
Đây là một triển khai trong Ruby.
def find_number_via_linear_search(array, target)
counter = 0
# iterate through the given array starting
# at index 0 and continuing until the end
while counter < array.length
if array[counter] == target
# exit if target element found
return "linear search took: #{counter} iterations"
else
counter += 1
end
end
return "#{target} not found"
end
Chúng tôi có thể cung cấp cho phương pháp này một vòng quay như sau:
# Let's create an array with 50 integers
# and then re-arrange the order to make
# things more interesting
array = [*1..50].shuffle
find_number_via_linear_search(array, 24)
Tôi đã chạy điều này một vài lần và nhận được kết quả sau:
=> "linear search took: 10 iterations"
=> "linear search took: 11 iterations"
=> "linear search took: 26 iterations"
Khi phân tích ký hiệu Big-O của một hàm, chúng tôi quan tâm đến trường hợp xấu nhất (còn gọi là giới hạn tiệm cận trên).
Suy nghĩ về điều này một cách trực quan, số lần lặp nhỏ nhất sẽ là 1. Điều đó xảy ra khi phần tử đích ở vị trí 0 trong mảng. Số lần lặp lớn nhất (hoặc trường hợp xấu nhất) sẽ là 50. Điều này sẽ xảy ra khi phần tử đích không được tìm thấy trong mảng.
Nếu mảng của chúng ta có 100 phần tử, trường hợp xấu nhất sẽ là 100 lần lặp. 200 phần tử? 200 lần lặp. Do đó, ký hiệu Big-O cho tìm kiếm tuyến tính đơn giản là O (n), trong đó n là số phần tử.
Một ví dụ phức tạp hơn với tìm kiếm nhị phân!
Hãy xem xét tìm kiếm nhị phân tiếp theo. Đây là cách bạn thực hiện tìm kiếm nhị phân được sắp xếp trước mảng:1. Lấy yếu tố ở giữa
2. If element == target chúng tôi đã hoàn thành 3. If element > target loại bỏ nửa trên của mảng 4. Nếu element < target loại bỏ nửa dưới của mảng 5. Bắt đầu lại ở bước 1 với mảng còn lại
Lưu ý:Nếu bạn là người theo chủ nghĩa Ruby, có một phương pháp tìm kiếm b tích hợp sẵn để thực hiện thuật toán này cho bạn!
Ví dụ:giả sử bạn có một cuốn từ điển và bạn đang tìm kiếm "quả dứa" trên thế giới. Chúng ta sẽ đến trang giữa của từ điển. Nếu tình cờ có thế giới "quả dứa", chúng ta đã xong!
Nhưng tôi đoán là, phần giữa của từ điển vẫn chưa có chữ "p" nên có lẽ chúng ta sẽ tìm thấy từ "llama." Chữ "L" đứng trước "P" nên chúng tôi sẽ loại bỏ toàn bộ nửa dưới của từ điển. Tiếp theo, chúng tôi sẽ lặp lại quy trình với những gì còn lại.
Như với tìm kiếm tuyến tính, thời gian chạy trường hợp tốt nhất cho tìm kiếm nhị phân là một lần lặp lại. Nhưng trường hợp xấu nhất là gì? Đây là một ví dụ về mảng có 16 phần tử - giả sử chúng ta muốn sử dụng tìm kiếm nhị phân để tìm số 23:
[2, 3, 15, 18, 22, 23, 24, 50, 65, 66, 88, 90, 92, 95, 100, 200]
Bước đầu tiên là xem số ở chỉ số 7, là 50. Vì 50 lớn hơn 23, chúng tôi loại bỏ mọi thứ ở bên phải. Bây giờ mảng của chúng ta trông như thế này:
[2, 3, 15, 18, 22, 23, 24, 50]
Phần tử giữa bây giờ là 18, nhỏ hơn 23, vì vậy chúng tôi loại bỏ nửa dưới lần này.
[22, 23, 24, 50]
Cái nào trở thành
[22, 23]
Cuối cùng trở thành
[23]
Tổng cộng, chúng tôi phải chia mảng làm đôi 4 lần để tìm số mà chúng tôi đang nhắm mục tiêu trong mảng, có độ dài là 16.
Để tổng quát hóa điều này, chúng ta có thể nói rằng trường hợp xấu nhất cho tìm kiếm nhị phân là số lần tối đa chúng ta có thể chia mảng làm đôi.
Trong toán học, chúng ta sử dụng logarit để trả lời câu hỏi, "Chúng ta nhân với bao nhiêu số trong số này để được số đó?" Đây là cách chúng tôi áp dụng logarit cho vấn đề của mình:
Do đó, chúng ta có thể nói rằng Big-O, hoặc thời gian chạy trong trường hợp xấu nhất cho một tìm kiếm nhị phân, là log (cơ số 2) n.
Kết thúc
Ký hiệu Big-O là một cách ưa thích để nói, "Này, trường hợp xấu nhất cho điều này là gì?" Đặt khoa học máy tính sang một bên, một ví dụ trong thế giới thực có thể là điều xảy ra khi bạn hỏi thợ sửa ống nước của mình sẽ tốn bao nhiêu tiền để sửa vòi nước bị hỏng. Anh ta có thể trả lời, "Chà, tôi có thể đảm bảo rằng nó sẽ không quá 2.000 đô la." Đây là giới hạn trên, mặc dù không hữu ích cho bạn.
Do đó, các ký hiệu Big-O khác thường được sử dụng. Ví dụ, Big-Theta quan tâm đến cả giới hạn dưới và giới hạn trên. Trong trường hợp này, người thợ sửa ống nước sẽ trả lời, "Chà, nó sẽ không dưới 1.000 đô la nhưng sẽ không quá 2.000 đô la." Điều này hữu ích hơn nhiều.
Cảm ơn bạn đã đọc và tôi hy vọng rằng bài đăng này đã giúp làm cho ký hiệu Big-O ít nhất là một chủ đề bớt đáng sợ hơn một chút!