Hướng dẫn list remove time complexity python - danh sách loại bỏ phức tạp thời gian python
|
Show
Tổng quanChúng tôi đã thảo luận về phương pháp Danh sách Trước khi thảo luận về sự phức tạp về thời gian và không gian, hãy để nhanh chóng nhớ lại phương pháp này là gì. list.remove()________ 7 & nbsp; xóa sự xuất hiện đầu tiên của phần tử & nbsp; ________ 8 & nbsp; từ danh sách. Nếu phần tử không có trong danh sách, nó sẽ ném & nbsp; valueError; Phương thức này cũng mong đợi một tham số tức là giá trị sẽ được xóa khỏi danh sách, nhưng khi không có tham số nào được truyền cho nó, nó sẽ ném & nbsp; typeerror.ValueError; the method also expects a parameter i.e the value to be removed from the list, but when no parameter is passed to it, it throws the TypeError. Phân tích độ phức tạp thời gian và không gian của phương thức xóa danh sách ()Độ phức tạp về thời gian Độ phức tạp về thời gianĐộ phức tạp không gianO(N), where N is the size of the list. Bài đăng này có hữu ích không? # Replicating the behavior of list.remove() method.
def list_remove(li,element = None):
if element == None: # If no value provided for deletion, throw a TypeError
raise TypeError("TypeError: list_remove() takes exactly one argument (0 given)")
for idx,ele in enumerate(li):
if element == ele: # Element found? Delete it from the list
del li[idx] # Delete the element from the list
return # Return after deleting the element
raise ValueError("item not found") # If the element not found in the list, raise the ValueError
# Driver code
if __name__ == "__main__":
list = [1,2,2,3,22] # Sample List
print("List before deleting element {}".format(list))
remove_element = 2 # Element to be removed
list_remove(list,remove_element) # Call the deletion on list
print("List after deleting element {}".format(list))Độ phức tạp không gianBài đăng này có hữu ích không?O(1) operation so are the item shifts, hence the space complexity of the algorithm is O(1). Chúng tôi đã thảo luận về phương pháp Danh sách Trước khi thảo luận về sự phức tạp về thời gian và không gian, hãy để nhanh chóng nhớ lại phương pháp này là gì.Nếu bạn đang học Python sau JavaScript là ngôn ngữ đầu tiên của bạn. Bạn có thể sẽ bị khóa bởi các chức năng sẵn có mà chúng ta có trong Python. Trong khi xóa bất kỳ yếu tố nào khỏi danh sách, chúng tôi nên quan tâm đến sự phức tạp và chúng tôi có chức năng pop () bật phần tử từ danh sách trên chỉ mục được cung cấp. Nó có quan tâm đến sự phức tạp về thời gian không? Hãy xem xét chúng tôi có danh sách sau. a = [1, 2, 3, 4, 5, 6]Bằng cách thực hiện a = [1, 2, 3, 4, 5, 6]2 không có đối số, nó sẽ xóa và trả về phần tử cuối cùng có độ phức tạp thời gian O (1). Bởi vì nó chỉ loại bỏ phần tử cuối cùng và không cần phải sắp xếp lại các phần tử.Danh sách Python được thực hiện như một mảng của con trỏ. Nếu chúng ta thực hiện xóa và trả lại a = [1, 2, 3, 4, 5, 6]4 và sau đó di chuyển tất cả các yếu tố sau khi a = [1, 2, 3, 4, 5, 6]5 lên một vị trí. Để chúng tôi không có giá trị a = [1, 2, 3, 4, 5, 6]6 ở vị trí a = [1, 2, 3, 4, 5, 6]7.Vì vậy, điều gì sẽ là sự phức tạp về thời gian khi chúng ta vượt qua một cuộc tranh luận? Hãy xem xét độ dài của danh sách là a = [1, 2, 3, 4, 5, 6]8 và chúng ta cần loại bỏ một phần tử tại a = [1, 2, 3, 4, 5, 6]9 vị trí như sau.a.pop(k)Công thức chung cho độ phức tạp thời gian này sẽ là:general formula for this time complexity will be: O(N-k)Độ phức tạp thời gian tồi tệ nhất sẽ là: time complexity will be:
Độ phức tạp thời gian trường hợp trung bình sẽ là: time complexity will be: O(k) or O(N/2)Vì chúng tôi có sáu yếu tố trong danh sách và loại bỏ phần tử giữa của danh sách là a.pop(k)0 trong đó sẽ có các hoạt động a = [1, 2, 3, 4, 5, 6]5. Vì vậy, đơn giản là chúng ta sẽ có độ phức tạp thời gian a.pop(k)222Verage.Nhìn vào sự phức tạp, chúng ta không nên sử dụng a.pop(k)3 để quản lý hàng đợi. Thay vào đó chúng tôi có a.pop(k)4in Python.Hạnh phúc mã hóa cho đến lúc đó! Độ phức tạp thời gian của việc loại bỏ trong Python là gì?Độ phức tạp thời gian chạy của tập hợp.loại bỏ () hàm trên một tập hợp với n phần tử là O (1).Vì vậy, bộ của Python.phương thức loại bỏ () có độ phức tạp thời gian chạy không đổi.O(1). So, Python's set. remove() method has constant runtime complexity.
Danh sách Python có phải là Pop O 1 không?Có, đó là O (1) để bật phần tử cuối cùng của danh sách Python và O (n) để bật một yếu tố tùy ý (vì toàn bộ phần còn lại của danh sách phải được thay đổi).Vì vậy, chỉ để làm cho nó rõ ràng, danh sách.pop (0) là o (n) và danh sách.pop () là O (1)., and O(N) to pop an arbitrary element (since the whole rest of the list has to be shifted). So just to make it clear, list. pop(0) is O(n) and list. pop() is O(1).
Có đang xóa một phần tử O 1 không?Loại bỏ một phần tử ở cuối là O (1) vì không có sự thay đổi. because there is no shifting.
Sự khác biệt giữa các phương thức danh sách pop () và xóa () là gì?Hàm Remove () Xóa giá trị khớp đầu tiên khỏi danh sách. Hàm pop () được sử dụng để trả về phần tử bị xóa khỏi danh sách. The pop() function is used to return the removed element from the list. |
