I. Big O Notation là gì ?

Bạn đã có lần nghe nói đến các thuật toán nhanh và tác dụng khi triển khai một công việc gì đó, nhưng nhanh và tác dụng ở đây được xác minh ra sao?Phải chăng nó được đo bằng thời gian thực hiện nay xong quá trình đó vào vài giây xuất xắc vài phút tốt không? Câu trả lời là không thưa các bạn!

Chương trình trên sản phẩm công nghệ tính của bản thân mình chạy lờ lững hơn trên laptop của các bạn chính vì mình đang áp dụng một máy tính cũ hoặc bởi vì trong dịp chạy lịch trình này bản thân còn chạy rất nhiều chương trình khác nữa,…Vì thế, khi công tác trên sản phẩm công nghệ tính của mình chạy chậm hơn trên vật dụng tính của công ty không có nghĩa là bạn đang sử dụng một thuật toán công dụng hơn của mình.Do đó, khi so sánh hai thuật toán ngẫu nhiên thực hiện cho 1 tác vụ làm sao đó, bọn họ không thể phụ thuộc thời gian triển khai tác vụ đó.

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

II. Lấy ví dụ ?

Để giải quyết và xử lý vấn đề này, định nghĩa Big O Notation đang được giới thiệu để định nghĩa, thống kê giám sát tính hiệu quả của một thuật toán. Nó nhờ vào số bước cần triển khai của một thuật toán cho một tác vụ nào kia để tính toán tính kết quả của thuật toán đó. Rõ ràng nó như vậy nào, họ hãy thuộc xem xét những ví dụ sau nhé:

func getLastNumber(numb <>int) int return numbCác bước tiến hành trong cách làm trên là:

Lấy nằm trong tính length của mảng numb (1)Thực hiện nay phép tính len(numb) – 1 (2)Sau lúc có công dụng ở bước (2) thì lấy giá trị tại index này vào mảng numb. (3)Và sau cùng là return lại kết quả. (4)Như vậy, phương thức trên, thuật toán của họ sẽ trải qua toàn bộ 4 bước cho dù con số dữ liệu vào mảng numb bao gồm lớn như vậy nào!

Nếu quy về dạng hàm số mà chúng ta đã được học ở nhiều thì bạn có thể biểu diễn thuật toán bên trên như sau:

f(n) = 4với n là số lượng dữ liệu trong mảng của chúng ta.

Hãy chú ý ví dụ thiết bị hai nhé những bạn:

func sum(numb <>int) int {sum := 0for i := 0; i Với lấy ví dụ này, bạn cũng có thể xác định số bước cần tiến hành của thuật toán này như sau:

Ở không tính vòng lặp for, bọn họ có 3 cách bao gồm:Khởi tạo thay đổi sum với mức giá trị 0Khởi tạo biến i với giá trị 0Return lại giá trị của biến hóa sumTrong vòng lặp for, với mỗi phần tử trong mảng numb thì bọn họ lại có các bước như sau:Lấy nằm trong tính length của mảng numb (1)So sánh hiệu quả của cách (1) với biến hóa i (2)Lấy giá trị của mảng numb tại index i (3)Cộng biến đổi sum với cái giá trị tại cách (4)Gán giá trị ở cách (4) vào lại đổi thay sum (5)Tăng cực hiếm của biến hóa i lên 1 (6)Như vậy, trong vòng lặp for, cùng với mỗi phần tử trong mảng numb, bọn họ có 6 bước yêu cầu thực hiện. N là số phần tử trong mảng numb thì bọn họ có 6n bước đề xuất thực hiện.

Tổng cộng, họ có 6n + 3 cách cần triển khai cho thuật toán trong cách thức này. Bên dưới dạng hàm số, bạn có thể biểu diễn như sau:

f(n) = 6n + 3Như vậy, như các bạn thấy, với ví dụ sản phẩm nhất, ví dụ số cách cần thực hiện không phụ thuộc vào số lượng dữ liệu mà họ đưa vào. Còn sống ví dụ lắp thêm hai, tài liệu đưa vào của chúng ta càng khủng thì số bước cần thực hiện của họ lại tăng theo.

Và ở đây, các các bạn sẽ thấy, bọn họ sẽ có một hàm g(n) khác sao cho tính từ lúc một giá trị n >= n0, cực hiếm của hàm g(n) nhân với cùng một hằng số nào kia c0 luôn luôn luôn lớn hơn giá trị của hàm f(n). Lúc đó, hàm g(n) điện thoại tư vấn là cận bên trên của hàm f(n) và hàm f(n) điện thoại tư vấn là Big O của hàm g(n), viết là f(n) = O(g(n)).

Trong ví dụ đồ vật hai, bạn có thể gọi hàm g(n) = n là Big O của hàm f(n) = 6n + 3. Chính vì ở đây, khi quý hiếm của n0 >= 3, c0 = 7 thì:f(n) = 21c0 * g(n) = 21giá trị của hàm f(n) luôn nhỏ hơn hoặc bởi giá trị của hàm g(n) nhân với cùng 1 hằng số c0.

Chúng ta hoàn toàn có thể định nghĩa của Big O Notation như sau:

f(n) = O(g(n)) lúc tồn tại một n0 > 0 với c0 > 0 sao cho:f(n) = n0.Trong ví dụ sản phẩm công nghệ nhất, thì f(n) là một trong những Big O của một hằng số, call là O(1).

Ở ví dụ đồ vật hai thì f(n) là 1 Big O của n, hotline là O(n).

Xem thêm: Hướng Dẫn Giải Bài Tập Hình Học 10 Hay Nhất, Ngắn Gọn, Giải Bài Tập Hình Học Lớp 10 Chi Tiết, Dễ Hiểu

Như vậy, Big O Notation là một trong khái niệm để xác định kỹ năng mở rộng lớn của một thuật toán phụ thuộc vào số bước triển khai của thuật toán đó. Chúng ta có thể dự đoán được thuật toán đó với tài liệu ngày càng mập thì sẽ như vậy nào. Và mang đến phép họ ước lượng được trường vừa lòng xấu nhất phụ thuộc vào cận bên trên của thuật toán này.

III. Big-O Complexity Chart

*

IV. Common Complexity Algorithm

*
*

IV. Mối cung cấp tham khảo

WikiComplexity ChartExample