Big-O của danh sách cắt

Question

Giả sử tôi có một số danh sách Python, my_list có chứa N phần tử. Các phần tử đơn lẻ có thể được lập chỉ mục bằng cách sử dụng my_list[i_1], trong đó i_1 là chỉ mục của phần tử mong muốn. Tuy nhiên, danh sách Python cũng có thể được lập chỉ mục my_list[i_1:i_2] trong đó một "lát" của danh sách từ i_1 đến i_2 là mong muốn. Ký hiệu Big-O (trường hợp xấu nhất) để chia danh sách kích thước N là gì?

Cá nhân, nếu tôi đã mã hóa "slicer", tôi sẽ lặp lại từ i_1 đến i_2, tạo danh sách mới và trả về, ngụ ý O (N), đây có phải là cách Python thực hiện không?

Cảm ơn bạn,

Answer 1

Lấy một lát là O (i_2 - i_1). Điều này là do biểu diễn nội bộ của Python trong danh sách là một mảng, vì vậy bạn có thể bắt đầu tại i_1 và lặp lại thành i_2.

Để biết thêm thông tin, vui lòng xem Python time complexity wiki entry

Bạn cũng có thể nhìn vào thực hiện trong CPython source nếu bạn muốn.

Answer 2

Để biết danh sách có kích thước N và một lát có kích thước M, lần lặp thực sự chỉ là O (M), chứ không phải O (N). Vì M thường là < < N, điều này tạo nên sự khác biệt lớn.

Thực tế, nếu bạn nghĩ về lời giải thích của mình, bạn có thể thấy lý do. Bạn chỉ đang lặp từ i_1 đến i_2, không phải từ 0 đến i_1, sau đó là I_1 đến i_2.

Answer 3

theo http://wiki.python.org/moin/TimeComplexity

nó là O (k) với k là kích thước lát