Hướng dẫn python o(1) lookup - tra cứu python o(1)

Tôi hiểu rằng một danh sách khác với một mảng. Nhưng vẫn vậy, O (1)? Điều đó có nghĩa là truy cập một yếu tố trong danh sách sẽ nhanh như truy cập một yếu tố trong một dict, mà tất cả chúng ta đều biết là không đúng. Câu hỏi của tôi dựa trên tài liệu này:

list

----------------------------
| Operation | Average Case |
|-----------|--------------|
|    ...    |     ...      |
|-----------|--------------|
|  Get Item |     O(1)     |
----------------------------

Và câu trả lời này:

Tra cứu trong danh sách là O (N), tra cứu trong từ điển được khấu hao o (1), liên quan đến số lượng các mục trong cấu trúc dữ liệu.

Nếu tài liệu đầu tiên là đúng, thì tại sao việc truy cập một dict nhanh hơn truy cập danh sách nếu chúng có cùng độ phức tạp?

Có ai có thể đưa ra một lời giải thích rõ ràng về điều này xin vui lòng? Tôi muốn nói rằng nó luôn phụ thuộc vào quy mô của danh sách/dict, nhưng tôi cần hiểu biết thêm về điều này.

Khi được hỏi ngày 20 tháng 5 năm 2016 lúc 15:33May 20, 2016 at 15:33

4

Get Item đang nhận một mục trong một chỉ mục cụ thể, trong khi Tra cứu có nghĩa là tìm kiếm nếu một số yếu tố tồn tại trong danh sách. Để làm như vậy, trừ khi danh sách được sắp xếp, bạn sẽ cần lặp lại tất cả các yếu tố và có các hoạt động mục O(n), dẫn đến tra cứu O (n).

Một từ điển đang duy trì cấu trúc dữ liệu thông minh (bảng băm) dưới mui xe, do đó bạn sẽ không cần truy vấn O(n) lần để tìm nếu phần tử tồn tại, nhưng số lần không đổi (trường hợp trung bình), dẫn đến tra cứu O(1).

PVG

2.6524 Huy hiệu vàng16 Huy hiệu bạc31 Huy hiệu Đồng4 gold badges16 silver badges31 bronze badges

Đã trả lời ngày 20 tháng 5 năm 2016 lúc 15:35May 20, 2016 at 15:35

7

Truy cập danh sách l tại INDEX n l[n] là O (1) vì nó không được triển khai như một danh sách liên kết vani trong đó người ta cần nhảy giữa các con trỏ (giá trị, tiếp theo->) n lần để tiếp cận chỉ mục ô n.

Nếu bộ nhớ liên tục và kích thước mục nhập sẽ được sửa, việc đạt được một mục cụ thể sẽ là tầm thường như chúng ta biết để nhảy n lần kích thước mục nhập (như các mảng cổ điển trong C).

Tuy nhiên, vì danh sách có thể thay đổi về kích thước mục, việc triển khai Python sử dụng danh sách bộ nhớ liên tục chỉ cho các con trỏ cho các giá trị. Điều này làm cho việc lập chỉ mục một danh sách (l [n]) một hoạt động có chi phí độc lập với kích thước của danh sách hoặc giá trị của chỉ mục.

Để biết thêm thông tin, xem http://effbot.org/pyfaq/how-are-lists-implemented.htm

Đã trả lời ngày 22 tháng 6 năm 2019 lúc 18:13Jun 22, 2019 at 18:13

Hanan Shteingarthanan ShteingartHanan Shteingart

7.9298 Huy hiệu vàng47 Huy hiệu bạc63 Huy hiệu Đồng8 gold badges47 silver badges63 bronze badges

Đó là bởi vì Python lưu trữ địa chỉ của mỗi nút của một danh sách thành một mảng riêng biệt. Khi chúng ta muốn một phần tử tại NTH Node, tất cả những gì chúng ta phải làm là tra cứu phần tử thứ n của mảng địa chỉ cung cấp cho chúng ta địa chỉ của nút thứ n của danh sách mà chúng ta có thể nhận được giá trị của nút đó trong độ phức tạp của O(1).

Python thực hiện một số thủ thuật gọn gàng để làm cho các mảng này có thể mở rộng khi danh sách phát triển. Do đó, chúng tôi đang có được sự linh hoạt của danh sách và tốc độ của các mảng. Việc đánh đổi ở đây là trình biên dịch phải phân bổ lại bộ nhớ cho mảng địa chỉ bất cứ khi nào danh sách phát triển đến một mức độ nhất định.

Amit đã giải thích trong câu trả lời của mình cho câu hỏi này về lý do tại sao tra cứu trong từ điển nhanh hơn trong danh sách.

Đã trả lời ngày 10 tháng 5 năm 2020 lúc 7:18May 10, 2020 at 7:18

FaihanfaihanFaihan

Huy hiệu đồng 931 Bạc6 Huy hiệu Đồng1 silver badge6 bronze badges

Tối thiểu có thể tôi có thể thấy là o (log n) từ quan điểm khoa học máy tính nghiêm ngặt

Đã trả lời ngày 12 tháng 10 năm 2017 lúc 22:07Oct 12, 2017 at 22:07

Dave Crookedave CrookeDave Crooke

6401 Huy hiệu vàng6 Huy hiệu bạc12 Huy hiệu đồng1 gold badge6 silver badges12 bronze badges

6