Big O là gì?
Ký hiệu Big O được sử dụng để định lượng thời gian chạy hoặc sử dụng bộ nhớ sẽ tăng nhanh như thế nào khi một thuật toán chạy, trong trường hợp xấu nhất, liên quan đến kích thước của dữ liệu đầu vào ( n ). Nó cũng đôi khi được gọi là cận trên của tiệm cận.
Chúng ta có thể sử dụng ký hiệu Big O để mô tả hai điều:
- Độ phức tạp
về thời gian Thời gian của thuật toán phát triển nhanh như thế nào, so với đầu vào - Độ phức tạp về
không gian Thuật toán yêu cầu bao nhiêu không gian khi nó phát triển
Hướng dẫn này sẽ hướng dẫn bạn cách sử dụng ký hiệu Big O , với các mẫu mã được chú thích rõ ràng.
- Tại sao sử dụng Big O?
- Cách tính Big O
- Các chức năng Big O thường gặp
- Thời gian phức tạp
- Không gian phức tạp
- Trường hợp tốt nhất, trung bình và xấu nhất
- Big O cho cấu trúc dữ liệu
- Big O cho các hoạt động Python
- Các nguồn hữu ích khác
Tại sao sử dụng Big O?
Đối với bất kỳ vấn đề nhất định, có thể có một loạt các giải pháp. Nhưng nếu bạn đo thời gian thực hiện bằng cách sử dụng giây, bạn sẽ phải đối mặt với những biến động do các yếu tố vật lý gây ra. Điều này bao gồm dung lượng bộ nhớ trên máy được sử dụng để chạy giải pháp, tốc độ CPU và các chương trình khác chạy đồng thời trên hệ thống.
Big O được sử dụng để so sánh hiệu quả của một giải pháp, không bao gồm các yếu tố vật lý.
Mỗi thuật toán mang những phức tạp về không gian và thời gian riêng của nó. Trong nhiều tình huống, giải pháp tốt nhất sẽ là sự cân bằng của cả hai.
Ví dụ: nếu chúng ta cần một giải pháp nhanh và chúng ta không quá lo lắng về yêu cầu không gian, thì sự cân bằng có thể chấp nhận được có thể là một thuật toán có độ phức tạp thời gian thấp hơn và độ phức tạp không gian cao hơn. ví dụ: Merge Sort.
Vì vậy, làm thế nào để bạn tính toán Big O cho một thuật toán nhất định?
Cách tính Big O
Để tính toán Big O, trước tiên bạn cần xem xét có bao nhiêu hoạt động đang được thực hiện.
Hướng dẫn 5 bước đơn giản:
- Chia thuật toán của bạn thành các hoạt động
- Tính toán O lớn của mỗi hoạt động
- Thêm Big O từ mỗi hoạt động
- Loại bỏ các hằng số
- Tìm điều khoản đặt hàng cao nhất
Các ví dụ dưới đây sẽ hướng dẫn bạn chi tiết từng bước, nhưng điều đáng nói là tại sao chúng tôi loại bỏ các hằng số.
Định nghĩa của chúng tôi về Big O bao gồm cụm từ 'liên quan đến kích thước của dữ liệu đầu vào ( n )'. Điều này có nghĩa là khi n nhận được các phép toán có kích thước cố định, lớn tùy ý, chẳng hạn như cộng 100 hoặc chia cho 2, có ảnh hưởng giảm dần đáng kể đến thời gian thực thi một thuật toán.
Có lý do tương tự đằng sau lý do tại sao chúng tôi tìm kiếm thuật ngữ quan trọng nhất. Big O đo lường trường hợp xấu nhất, có nghĩa là chúng ta nên luôn sử dụng độ phức tạp thời gian chậm nhất cho bất kỳ hoạt động nào trong một thuật toán. Khi n lớn tùy ý, các thuật ngữ ít quan trọng hơn sẽ không có tác động đến thời gian chạy như thuật ngữ quan trọng nhất.
Ví dụ 1: Cộng hai số
Trong ví dụ 1, chúng tôi đang thêm hai số từ một danh sách nhất định, bằng cách thực hiện tra cứu chỉ mục.
Vì total = nums[0] + nums[1], chúng tôi đang thực hiện ba phép toán, mỗi phép toán có độ phức tạp thời gian không đổi là O (1):
- Hoạt động 1:
nums [0] - Đây là một tra cứu. O (1) - Hoạt động 2:
nums [1] - Đây là một tra cứu. O (1)
Thao tác 3: total = nums [0] + nums [1] - Đây là một phép gán. O (1)
Sau đó return total, chúng tôi , đó là một phép toán O (1) khác. Do đó, số hạng bậc cao nhất trong ví dụ này là O (1).
Ví dụ 2: Các vòng lặp đơn giản
Thêm các ký hiệu này cho từng thao tác trong số ba thao tác, chúng tôi nhận được:
O(1 + n/2 + 1/2n + 10)Khi các hằng số bị loại bỏ, điều này sẽ loại bỏ các giá trị 1, / 2, 1/2 và 10. Vì vậy, chúng tôi nhận được:
O(n)Hằng số bị loại bỏ vì chúng có tầm quan trọng thấp hơn đáng kể khi chúng ta tiến gần đến vô hạn.
Big O cuối cùng của một thuật toán chứa nhiều phép toán, là phép toán có độ phức tạp cao nhất.
Các chức năng Big O phổ biến
Các ví dụ trên đã giới thiệu nhanh về cách chúng tôi tính toán Big O cho một thuật toán nhất định. Nhưng O (1), O (n) và các độ phức tạp khác thực sự có nghĩa là gì?
Một số chức năng phổ biến nhất là:
| Tên | Big-O |
|---|---|
| Không thay đổi | O (1) |
| Lôgarit | O (log (n)) |
| Tuyến tính | O(n) |
| Nhật ký tuyến tính | O (n log (n)) |
| Bậc hai | O(n^2) |
| Khối | O(n^3) |
| số mũ | O(2^n) |
Thời gian phức tạp
Thời gian không đổi: O (1)
Các thuộc tính của thuật toán có độ phức tạp thời gian không đổi
- Thời gian thực hiện thuật toán không phụ thuộc vào kích thước của dữ liệu đầu vào
- Độ phức tạp về thời gian luôn giống nhau, bất kể đầu vào là gì
Một số hoạt động với độ phức tạp thời gian O (1):
- lấy vật phẩm (tra cứu theo chỉ mục / khóa)
- thiết lập mục (chuyển nhượng)
- một phép toán số học (ví dụ: 1 + 1, 2 - 1, v.v.)
- kiểm tra so sánh (ví dụ: x == 1)
Bất kỳ phương thức nào thực hiện một số hoạt động cơ bản cố định mỗi khi nó được gọi đều yêu cầu thời gian không đổi.
Khi truy xuất giá trị của một phần tử tại một chỉ mục cụ thể, độ phức tạp về thời gian là O (1). Trong ví dụ trên, cho dù danh sách của chúng ta chứa 5 phần tử hay 500, thì độ phức tạp của việc truy xuất giá trị tại chỉ mục 0 vẫn là O (1).
Lý do cho điều này là vì các hoạt động cần thiết để truy cập một phần tử trong bộ nhớ không đổi, bất kể có bao nhiêu phần tử trong mảng.
Với địa chỉ bộ nhớ bắt đầu của một mảng, bạn có thể chỉ cần nhân kích thước của kiểu dữ liệu tính bằng byte với chỉ mục của mục bạn đang tìm kiếm.
Ví dụ: Địa chỉ bắt đầu của mảng là 10. Tìm kiếm phần tử thứ 5 trong mảng các số nguyên. Kiểu dữ liệu số nguyên là 4 byte. Vì vậy, địa chỉ của mặt hàng chúng tôi đang tìm kiếm là:(10 + (5 * 4))
Thời gian lôgarit: O (log n)
Các thuộc tính của thuật toán có độ phức tạp theo thời gian logarit :
- Giảm kích thước của dữ liệu đầu vào trong mỗi bước
- Không cần phải nhìn vào tất cả các giá trị
- Hành động tiếp theo sẽ chỉ được thực hiện trên một trong số các yếu tố có thể có
Các phép toán ví dụ: Tìm kiếm nhị phân, các phép toán trên cây tìm kiếm nhị phân
Các thuật toán có cách tiếp cận 'chia để trị' được coi là có độ phức tạp theo thời gian logarit, chẳng hạn như tìm kiếm nhị phân.
Ví dụ 1: In mọi giá trị thứ ba trong một phạm vi
Ví dụ 2: Tìm một giá trị bằng cách sử dụng tìm kiếm nhị phân
Thời gian tuyến tính: O (n)
Các thuộc tính của thuật toán có độ phức tạp theo thời gian tuyến tính :
- Số lượng các hoạt động diễn ra tỷ lệ tuyến tính với kích thước của n
- Ví dụ: Thực hiện thao tác in 100 lần, một lần cho mỗi mục, trong danh sách chứa 100 mục
Các thao tác ví dụ: sao chép, chèn vào một mảng, xóa khỏi một mảng, lặp lại
Thuật toán: Tìm kiếm tuyến tính
Một thuật toán có độ phức tạp thời gian tuyến tính được coi là giải pháp tối ưu khi tất cả các giá trị phải được kiểm tra.
Ví dụ 1: In mọi giá trị trong một dải ô
Trong ví dụ trên, bản thân hoạt động in là O (1), nhưng số lần lặp chúng ta thực hiện trong forvòng lặp tỷ lệ thuận với kích thước của dữ liệu đầu vào. Bởi vì chúng ta luôn lấy số hạng bậc cao hơn, độ phức tạp thời gian Big O là O (n).
Ví dụ 2: In mọi giá trị trong n hai lần, dưới dạng hai phép toán riêng biệt
Trong ví dụ 2, chúng tôi kết hợp hai độ phức tạp thời gian để có được O(n) + O(n) = O(2n). Bây giờ chúng ta bỏ hằng số (2) để có O (n).
Ví dụ 3: Tìm mục trong danh sách đã sắp xếp
Trong Ví dụ 3, chúng tôi đang thực hiện tìm kiếm tuyến tính trên một mảng được sắp xếp. Một cách tiếp cận nhanh hơn, vì mảng được sắp xếp, sẽ là sử dụng tìm kiếm nhị phân, có độ phức tạp thời gian logarit là O (log n).
Thời gian chuẩn tính: O (n log n)
Các thuộc tính của thuật toán có độ phức tạp thời gian tuyến tính log (còn được gọi là chuẩn tính ):
- Mỗi thao tác trong dữ liệu đầu vào có độ phức tạp về thời gian logarit
- ví dụ: đối với mỗi giá trị trong dữ liệu1 (O (n)) sử dụng tìm kiếm nhị phân (O (log n)) để tìm kiếm cùng một giá trị trong dữ liệu2
Các thao tác ví dụ: Sắp xếp danh sách
Các thuật toán có độ phức tạp thời gian O (n log n):
- Hợp nhất
- Đống
- Khối
Ví dụ 1:
Giờ bậc hai: O (n²)
Các thuộc tính của thuật toán có độ phức tạp thời gian bậc hai :
- Thực hiện phép toán thời gian tuyến tính cho mỗi giá trị trong dữ liệu đầu vào
- Đối với danh sách n mục, chúng ta thực hiện n thao tác cho mỗi mục. ví dụ: 10 mục có 10 ^ 2 phép toán.
Các phép toán ví dụ: Các vòng lặp lồng nhau.
Các thuật toán:
- Sắp xếp bong bóng
- Sắp xếp nhanh chóng
- Sắp xếp chèn
- Sắp xếp lựa chọn
- Phân loại cây
- Phân loại theo nhóm
Ví dụ 1: Vòng lặp lồng nhau
Thời gian theo cấp số nhân: O (2 ^ n)
Các thuộc tính của thuật toán có độ phức tạp theo thời gian hàm mũ :
- Tăng trưởng nhân đôi với mỗi lần bổ sung vào tập dữ liệu đầu vào
- ví dụ: vấn đề 'Towers of Hanoi'
Thuật toán: Fibonacci đệ quy
Ví dụ 1: Tính toán đệ quy các số Fibonacci
Thời gian giai thừa: O (n!)
Các thuộc tính của thuật toán có độ phức tạp thời gian giai thừa :
- Tăng trưởng theo cách dựa trên giai thừa dựa trên kích thước của dữ liệu đầu vào
- Phát triển nhanh chóng ngay cả đối với đầu vào kích thước nhỏ
Thuật toán: Thuật toán Heap - Được sử dụng để tạo ra tất cả các hoán vị có thể có của n đối tượng
Ví dụ 1: Thuật toán Heap
Không gian phức tạp
Trong một số tình huống, chúng tôi muốn tối ưu hóa không gian thay vì thời gian hoặc để tìm sự cân bằng giữa hai điều này. Đối với điều này, chúng ta cần tính toán độ phức tạp của không gian.
Độ phức tạp không gian được đo bằng cách sử dụng ký hiệu tương tự như độ phức tạp thời gian, nhưng chúng tôi xem xét tổng phân bổ bộ nhớ cần thiết, liên quan đến kích thước của đầu vào.
Ví dụ 1: Độ phức tạp không gian O (n)
Đoạn mã trên có độ phức tạp về không gian là O (n), vì lượng không gian cần thiết tăng theo kích thước của n (tuyến tính).
Ví dụ 2: Độ phức tạp không gian O (1)
Trong ví dụ 2, số lần chúng ta lặp qua vòng lặp tỷ lệ thuận với kích thước của đầu vào. Do đó, chúng ta có độ phức tạp thời gian tuyến tính là O (n).
Các printhoạt động đòi hỏi không gian liên tục, cho dù chúng ta gọi nó một lần hoặc 100 lần. Điều này có nghĩa là chúng ta có độ phức tạp không gian không đổi là O (1).
Trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất
Khi tính toán Big O, chúng tôi chỉ quan tâm đến trường hợp xấu nhất. Nhưng nó cũng có thể quan trọng để xem xét trường hợp trung bình và biết về trường hợp tốt nhất.
Ví dụ: khi tìm kiếm một giá trị trong mảng không được sắp xếp, trường hợp tốt nhất sẽ là giá trị đó là mục đầu tiên trong mảng. Điều này sẽ dẫn đến O (1). Ngược lại, nếu giá trị được tìm kiếm là mục cuối cùng trong mảng hoặc không có trong mảng, trường hợp xấu nhất sẽ là O (n).
Trường hợp tốt nhất: Tìm mục ở vị trí đầu tiên.
matcher(lst, 1) # O(1) - ConstantTrường hợp xấu nhất: Tìm mục ở vị trí cuối cùng.
matcher(lst,10) # O(n) - LinearBig O cho cấu trúc dữ liệu
Danh sách được Liên kết
So với mảng, danh sách được liên kết yêu cầu nhiều thời gian hơn, nhưng ít không gian hơn.
Danh sách được liên kết tiết kiệm trên bộ nhớ vì bạn chỉ tạo các mục bạn cần, không cần tạo trước một mảng có kích thước cố định cho một mảng tĩnh hoặc đối phó với quá trình sao chép đi kèm với một mảng động.
Nhược điểm là mất nhiều thời gian hơn để lấy các vật phẩm. Đó là bởi vì khi các nút được tạo, chúng có thể không gần nhau trong bộ nhớ. Điều này có nghĩa là chúng ta không thể thực hiện cùng một phép tính O (1) để xác định một giá trị cho chỉ số của nó, như chúng ta có thể làm với một mảng.
Với danh sách liên kết, khi truy xuất mục 'n' , chúng ta cần đi từ đầu danh sách đến mục thứ n . Do đó, truy xuất danh sách liên kết có độ phức tạp thời gian O lớn là O (n), là tuyến tính.
Logic tương tự cũng áp dụng cho việc thêm một mục mới vào danh sách được liên kết. Bạn cần đi từ đầu đến mục cuối cùng, sau đó đặt con trỏ 'tiếp theo' của mục cuối cùng làm nút mới. Đây là lý do tại sao phần phụ cũng được coi là thời gian O (n).
Ngược lại, thêm một mục vào đầu danh sách được liên kết là một phép toán thời gian không đổi O (1). Chúng ta chỉ cần đặt nút mới làm đầu của danh sách được liên kết, trỏ nó đến nút đầu trước đó. Số lượng hoạt động được thực hiện không bị ảnh hưởng bởi kích thước danh sách.
Cách duy nhất bạn có thể thực hiện thêm phép toán O (1) là duy trì một tham chiếu đến nút đuôi của danh sách được liên kết. Bằng cách này, bạn có thể:
- Tạo nút mới của bạn
- Đặt thuộc tính 'tiếp theo' của nút đuôi thành nút mới
- Đặt tham chiếu 'đuôi' để trỏ đến nút mới của bạn
Bảng băm
Độ phức tạp về thời gian của các thao tác trên bảng băm phụ thuộc nhiều vào chất lượng của hàm băm. Ngay cả khi giả sử hàm băm tính toán giá trị băm của một khóa trong thời gian không đổi O (1), nếu tất cả các giá trị băm vào cùng một vị trí và bạn sử dụng danh sách được liên kết để xử lý các xung đột, kết quả sẽ là tìm kiếm O (n).
Việc chèn vào bảng băm sẽ chỉ là O (1) nếu bạn sử dụng danh sách được liên kết để xử lý các xung đột và duy trì một con trỏ tới đuôi cho phần nối O (1).
Danh sách được liên kết gấp đôi
Ưu điểm chính của danh sách được liên kết kép (DLL) so với danh sách được liên kết đơn lẻ (SLL), xét về độ phức tạp về thời gian, là bạn có thể sử dụng chúng để tìm nút trước đó trong thời gian không đổi.
Với SLL, nếu chúng ta được cung cấp một nút và được yêu cầu tìm nút trước đó, chúng ta phải đi bộ từ đầu cho đến khi tìm thấy nút đã cho. Trong trường hợp xấu nhất, đây sẽ là O (n).
Mỗi nút trong DLL chứa một con trỏ đến nút trước đó, vì vậy chúng ta có thể chỉ cần sử dụng con trỏ này để truy xuất giá trị của nút trước đó trong thời gian O (1).
Big O cho các hoạt động Python
Liệt kê các hoạt động
Một số phương pháp danh sách thực hiện cùng một số thao tác cơ bản, không phân biệt kích thước danh sách, do đó, sử dụng độ phức tạp thời gian không đổi là O (1). Đối với các phương pháp danh sách khác, số lượng thao tác mà chúng thực hiện tỷ lệ với số lượng mục trong danh sách, vì vậy hãy sử dụng độ phức tạp thời gian tuyến tính của O (n).
Ví dụ đơn giản:
- O (1): Các
pop()phương pháp luôn luôn loại bỏ một mục vào cuối danh sách. Không quan trọng danh sách lớn như thế nào, chỉ cần thực hiện một thao tác. - O (n): Các
remove()phương pháp có để lấp đầy khoảng trống bằng cách di chuyển trên tất cả các mục ở bên phải của một trong đó đã được gỡ bỏ. Trong trường hợp xấu nhất, mục đầu tiên sẽ bị loại bỏ, có nghĩa là tất cả các mục trong danh sách cần phải được di chuyển.
Ví dụ phức tạp hơn: O (n): append()Phương thức thêm một mục vào cuối danh sách. Nếu bộ nhớ được cấp cho danh sách đã đủ lớn để chứa các mục hiện có và mục mới, thì độ phức tạp về thời gian sẽ không đổi O (1).
Tuy nhiên, nếu danh sách đã đầy trước đó append(), bạn cần phân bổ một mảng mới với kích thước đủ lớn để chứa tất cả các mục hiện có, cộng với mục bạn đang thêm. Python sau đó sẽ sao chép tất cả các mục từ mảng cũ sang mảng mới, làm cho độ phức tạp thời gian trong trường hợp xấu nhất tỷ lệ thuận với kích thước danh sách. Do đó, insert()phép toán danh sách có độ phức tạp thời gian tuyến tính là O (n).
| Hoạt động | Thí dụ | Big-O |
|---|---|---|
| Mục lục | danh sách [0] | O (1) |
| Cửa hàng | danh sách [0] = 0 | O (1) |
| Nối | list.append (4) | O (1) |
| Pop | list.pop () | O (1) |
| Thông thoáng | list.clear () | O (1) |
| Chiều dài | lanh (danh sách) | O (1) |
| Chỉ mục bật lên | list.pop (0) | O(n) |
| Tẩy | list.remove ('x') | O(n) |
| Chèn | list.insert (0, 'a') | O(n) |
| Của nhà điều hành | danh sách del | O(n) |
| Sự lặp lại | cho v trong danh sách: | O(n) |
| Sự ngăn chặn | 'x' trong danh sách1 | O(n) |
| Bình đẳng | list1 == list2 | O(n) |
| Sao chép | list.copy () | O(n) |
| Đảo ngược | list.reverse () | O(n) |
| lấy lát [x: y] | danh sách [a: b] | Đồng ý) |
| của lát | danh sách del [a: b] | O(n) |
| đặt lát | O(n+k) | |
| ghép lại | Đồng ý) | |
| Sắp xếp | list.sort () | O (n log n) |
| nhân | Danh sách 5 * | O(k n) |
Thao tác từ điển
| Hoạt động | Thí dụ | Big-O |
|---|---|---|
| Mục lục | dict [0] | O (1) |
| Cửa hàng | dict [0] = 'giá trị' | O (1) |
| Chiều dài | len(dict) | O (1) |
| Xóa bỏ | của dict [0] | O (1) |
| Được | dict.get (0) | O (1) |
| Pop | dict.pop () | O (1) |
| Mục pop | dict.popitem () | O (1) |
| Thông thoáng | dict.clear () | O (1) |
| Lượt xem | dict.keys () | O (1) |
| Sự lặp lại | cho k trong dict: | O(n) |
| Sự ngăn chặn | x trong dict: | O(n) |
| Sao chép | dict.copy () | O(n) |
Đặt hoạt động
Tập hợp có nhiều thao tác hơn là O (1) so với danh sách hoặc từ điển. Không phải giữ dữ liệu theo thứ tự làm giảm sự phức tạp.
| Hoạt động | Thí dụ | Big-O |
|---|---|---|
| Chiều dài | len(set) | O (1) |
| Thêm vào | set.add (4) | O (1) |
| Sự ngăn chặn | x trong bộ | O (1) |
| Tẩy | set.remove (4) | O (1) |
| Bỏ đi | set.discard (4) | O (1) |
| Pop | set.pop () | O (1) |
| Thông thoáng | set.clear () | O (1) |
| liên hiệp | set1 | set2 | O (len (s) + len (t)) |
| Ngã tư | set1 & set2 | O (len (s) + len (t)) |
| Sự khác biệt | set1 - set2 | O (len (s) + len (t)) |
| Sự khác biệt đối xứng | set1 ^ set2 | O (len (s) + len (t)) |
| Sự lặp lại | cho v trong bộ: | O(n) |
| Sao chép | set.copy () | O(n) |
Đăng nhận xét