Big-O z wycięciem listy

Question

Powiedz, że mam listę w języku Python, my_list, która zawiera N elementów. Pojedyncze elementy mogą być indeksowane za pomocą my_list[i_1], gdzie i_1 jest indeksem pożądanego elementu. Jednak listy Pythona mogą być również indeksowane my_list[i_1:i_2], gdzie pożądany jest "plaster" listy od i_1 do i_2. Co to jest notacja Big-O (najgorszy przypadek), aby wyciąć listę o rozmiarze N?

Osobiście, gdybym kodował "krajalnicę", chciałbym powtórzyć od i_1 do i_2, wygenerować nową listę i zwrócić ją, sugerując O (N), czy tak działa Python?

Dziękuję

Answer 1

Pierwsze kawałek jest O (i_2 - i_1). Dzieje się tak dlatego, że wewnętrzna reprezentacja list w Pythonie jest tablicą, więc możesz zacząć od i_1 i iterować do i_2.

Aby uzyskać więcej informacji, zobacz Python time complexity wiki entry

Można również spojrzeć na realizację w CPython source jeśli chcesz.

Answer 2

Dla listy o rozmiarze N i przekroju o rozmiarze M iteracja jest w rzeczywistości tylko O ​​(M), a nie O (N). Ponieważ M często jest < < N, robi to dużą różnicę.

W rzeczywistości, jeśli myślisz o swoim wyjaśnieniu, możesz zobaczyć, dlaczego. Wykonujesz tylko iterację od i_1 do i_2, a nie od 0 do i_1, a następnie od I_1 do i_2.

Answer 3

według http://wiki.python.org/moin/TimeComplexity

jest O (k), gdzie k jest wielkością plasterek