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:

  1. Độ 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
  2. Độ 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?

Đố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:

  1. Chia thuật toán của bạn thành các hoạt động
  2. Tính toán O lớn của mỗi hoạt động
  3. Thêm Big O từ mỗi hoạt động
  4. Loại bỏ các hằng số
  5. 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ố

def add_nums ( nums ) :
tổng = nums [ 0 ] + nums [ 1 ] # O (1) - Hằng số
trả về tổng số # O (1) - Hằng số
add_nums ([ 1 , 2 , 3 ])

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 totalchú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

def comp ( lst ) :
print ( lst [ 0 ]) # Hoạt động 1: O (1) - Hằng số
midpoint = len ( lst ) / 2 # Thao tác 2: O (n / 2)
cho val trong lst [ : midpoint ] : # Thao tác 3: O (1/2 * n)
in val
cho x trong phạm vi ( 10 ) : # Hoạt động 4: O (10)
print ( 'Xin chào Thế giới' )

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ênBig-O
Không thay đổiO (1)
LôgaritO (log (n))
Tuyến tínhO(n)
Nhật ký tuyến tínhO (n log (n))
Bậc haiO(n^2)
KhốiO(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.

Ví dụ 1: Nhận giá trị chỉ mục

def get_first ( dữ liệu ) :
trả về dữ liệu [ 0 ]
dữ liệu = [ 1 , 2 , 9 , 8 , 3 ]
print ( get_first ( dữ liệu ))

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

cho chỉ mục trong phạm vi ( 0 , len ( dữ liệu ) , 3 ) :
in ( dữ liệu [ chỉ mục ])

Ví dụ 2: Tìm một giá trị bằng cách sử dụng tìm kiếm nhị phân

def binarySearch ( sortedList, target ) :
left = 0
right = len ( sortedList ) - 1
while ( left < = right ) :
giữa = ( trái + phải ) / 2
if ( sortedList ( mid ) == target ) :
trở lại giữa
elif ( sortedList ( mid ) < target ) :
left = mid + 1
khác :
phải = giữa - 1
# Nếu mục tiêu không có trong danh sách, trả về -1
trả về -1
tìm kiếm nhị phân ([ 1 , 3 , 9 , 22 ] , 22 )
# trả lại 3


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 ô

dữ liệu = [ 1 , 7 , 3 , 19 , 2 , 100 ]
cho chỉ mục trong phạm vi ( len ( dữ liệu )) :
in ( dữ liệu [ chỉ mục ])

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

def print_twice ( lst ) : # O (n) - O (2n) nhưng chúng ta bỏ hằng số
cho val trong lst: # O (n)
in val
cho val trong lst: # O (n)
in val

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

def tuyến tínhSearch ( sortedList, target ) :
cho tôi trong phạm vi ( len ( sortedList )) :
if ( sortedList [ i ] == target ) :
trả lại tôi
# Nếu mục tiêu không có trong danh sách, trả về -1
trả về -1
Tìm kiếm tuyến tính ([ 1 , 3 , 9 , 22 ] , 22 )
# trả lại 3

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:

cho giá trị trong data1:
kết quả. append ( binary_search ( data2, value ))


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

cho x trong dữ liệu:
cho y trong dữ liệu:
print(x, y)


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

def fibonacci ( num ) :
if ( num < = 1 ) :
trả lại số
trả về fibonacci ( số - 2 ) + fibonacci ( số - 1 )


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

def heap_permutation ( data, n ) :
nếu n == 1 :
in ( dữ liệu )
trở về
đối với tôi trong phạm vi ( n ) :
heap_permutation ( dữ liệu, n - 1 )
nếu n% 2 == 0 :
data [ i ] , data [ n- 1 ] = data [ n- 1 ] , data [ i ]
khác :
data [ 0 ] , data [ n- 1 ] = data [ n- 1 ] , data [ 0 ]
dữ liệu = [ 1 , 2 , 3 ]
heap_permutation ( data, len ( data ))


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)

def create_list ( n ) :
new_list = []
cho num trong phạm vi ( n ) :
danh sách mới. chắp thêm ( 'mới' )
trả lại new_list
create_list ( 5 )
# ['mới', 'mới', 'mới', 'mới', 'mới']

Đ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)

def hello_world ( n ) :
cho x trong phạm vi ( len ( n )) : # Độ Phức tạp Thời gian - O (n)
print ( 'Hello World!' ) # Space Complexity - 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).

def matcher ( lst, match ) :
cho mục trong lst:
nếu mục == phù hợp:
trả về True
trả về Sai
lst = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ]

Trường hợp tốt nhất: Tìm mục ở vị trí đầu tiên.

matcher(lst, 1) # O(1) - Constant

Trường hợp xấu nhất: Tìm mục ở vị trí cuối cùng.

matcher(lst,10) # O(n) - Linear

Big 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ể:

  1. Tạo nút mới của bạn
  2. Đặt thuộc tính 'tiếp theo' của nút đuôi thành nút mới
  3. Đặ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 độngThí dụBig-O
Mục lụcdanh sách [0]O (1)
Cửa hàngdanh sách [0] = 0O (1)
Nốilist.append (4)O (1)
Poplist.pop ()O (1)
Thông thoánglist.clear ()O (1)
Chiều dàilanh (danh sách)O (1)
Chỉ mục bật lênlist.pop (0)O(n)
Tẩylist.remove ('x')O(n)
Chènlist.insert (0, 'a')O(n)
Của nhà điều hànhdanh sách delO(n)
Sự lặp lạicho v trong danh sách:O(n)
Sự ngăn chặn'x' trong danh sách1O(n)
Bình đẳnglist1 == list2O(n)
Sao chéplist.copy ()O(n)
Đảo ngượclist.reverse ()O(n)
lấy lát [x: y]danh sách [a: b]Đồng ý)
của látdanh sách del [a: b]O(n)
đặt látO(n+k)
ghép lạiĐồng ý)
Sắp xếplist.sort ()O (n log n)
nhânDanh sách 5 *O(k n)


Thao tác từ điển

Hoạt độngThí dụBig-O
Mục lụcdict [0]O (1)
Cửa hàngdict [0] = 'giá trị'O (1)
Chiều dàilen(dict)O (1)
Xóa bỏcủa dict [0]O (1)
Đượcdict.get (0)O (1)
Popdict.pop ()O (1)
Mục popdict.popitem ()O (1)
Thông thoángdict.clear ()O (1)
Lượt xemdict.keys ()O (1)
Sự lặp lạicho k trong dict:O(n)
Sự ngăn chặnx trong dict:O(n)
Sao chépdict.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 độngThí dụBig-O
Chiều dàilen(set)O (1)
Thêm vàoset.add (4)O (1)
Sự ngăn chặnx trong bộO (1)
Tẩyset.remove (4)O (1)
Bỏ điset.discard (4)O (1)
Popset.pop ()O (1)
Thông thoángset.clear ()O (1)
liên hiệpset1 | set2O (len (s) + len (t))
Ngã tưset1 & set2O (len (s) + len (t))
Sự khác biệtset1 - set2O (len (s) + len (t))
Sự khác biệt đối xứngset1 ^ set2O (len (s) + len (t))
Sự lặp lạicho v trong bộ:O(n)
Sao chépset.copy ()O(n)


Các tài nguyên hữu ích khác

Post a Comment

Mới hơn Cũ hơn