Zastanawiam się, jaka jest złożoność czasu metody pop obiektów listy w Pythonie (w szczególności w CPython). Również wartość N dla list.pop (N) wpływa na złożoność?Jaka jest złożoność czasu pojawiania się elementów z listy w Pythonie?
dla ostatniego elementu powinno być O (1), ponieważ wystarczy zwrócić element, do którego odnosi się ostatni element tablicy i zaktualizować indeks ostatniego elementu. Spodziewałbym się, że dowolny element będzie O (N) i wymagałby średnio N/2 operacji, ponieważ musiałbyś przenieść dowolne elementy poza element, który usuwasz jedną pozycję w tablicy wskaźników.
Tak, to jest O (1) pop ostatni element listy Python i O (N) do pop jest arbitralną elementu (ponieważ cała reszta listy musi zostać przesunięte).
Oto wielki artykuł na temat listy Python są przechowywane i manipulowane: http://effbot.org/zone/python-list.htm
Aby to wyjaśnić, list.pop (0) to O (n), a list.pop() to O (1). –
Aby uzyskać obie operacje w O (1), użyj collections.deque zobacz [tutaj] (https://wiki.python.org/moin/TimeComplexity) – galath
Odpowiedź jest krótka spojrzeć tutaj: https://wiki.python.org/moin/TimeComplexity
Bez argumentów pop swoją O (1)
z Argument pop:
Średnia złożoność czas:
każdym razem, gdy umieścić w wartość złożoności czasowej tej operacji to O (n - k).
Na przykład, jeśli masz listę 9 pozycji niż usunięcie z końca listy jest 9 operacje i oderwaniem od początku lista jest 1 operacji (usunięcie indeksu 0TH i przenoszenie wszystkich inne elementy do ich bieżącego indeksu - 1)
Ponieważ n - k dla środkowego elementu listy jest k operacji, średnia może być skrócona do O (k).
Innym sposobem, aby o tym pomyśleć, jest wyobrazić sobie, że każdy indeks został usunięty z listy 9 przedmiotów jeden raz. To byłoby w sumie 45 operacji. (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45)
45 jest równe O (nk), a ponieważ operacja pop wystąpiła O (n) razy dzielisz nk przez n aby uzyskać o (k)
zamortyzowany najgorszym przypadku złożoność czasowa
Wyobraź sobie, że masz listę 9 pozycji ponownie.Wyobraź sobie, że usuwasz wszystkie elementy z listy i pojawia się najgorszy przypadek, a za każdym razem usuwasz pierwszy element listy.
Ponieważ lista kurczy się o 1 za każdym razem, gdy liczba wszystkich operacji zmniejsza się za każdym razem od 9 do 1.
9 + 8 + 7 + 5 + 6 + 4 + 3 + 2 + 1 = 45 45 równa się O (nk). Ponieważ wykonałeś 9 operacji, a 9 to O (n), aby obliczyć amortyzowany scenariusz najgorszego scenariusza, wykonasz O (nk)/O (n), który jest równy O (k)
Podanie wartości O (n) dla średniej i najgorszy przypadek złożoność czasu jest również w pewnym sensie poprawna. Zauważ, że O (k) wynosi około O (1/2n) i upuszczenie stałej wynosi O (n)
najgorszym przypadku złożoność czasowa
zgadzam się z odpowiedzi udzielonej, ale wyjaśnienie jest imho źle. Możesz usunąć dowolny obiekt z listy w czasie O (1) (zasadniczo spraw, aby poprzedni wskaźnik wskazywał następny i usuń go) Problem polega na tym, że aby ZNALEŹĆ obiekt na tej pozycji, musisz przejść do tej listy point (zabiera czas O (N), nie wymaga uśredniania.) Na koniec specjalna uwaga przypadku :, pop (0) zajmie O (1), a nie O (0). – ntg
@nt lista jest tablicą wskaźników. aby usunąć wskaźnik z tablicy w środku, wszystkie wskaźniki po nim muszą być przesunięte w górę w tablicy, biorąc ilość czasu proporcjonalną do wielkości listy (którą oznaczamy jako N), a zatem będącą O (N) . Wyjaśnienie N w notacji Big-O NIE jest indeksem zwracanego elementu, ale funkcją ograniczającą czas działania algorytmu z O (1) będącym stałym czasem - tj. Nie zależy od wielkości Lista. O (N) oznacza, że funkcja graniczna jest trochę stała w stosunku do wielkości listy, f (n) = c * n + b. – tvanfosson
Ja się poprawiłem :) Rzeczywiście, implementacja list jest tablicą wskaźników. Twoja odpowiedź jest poprawna. Przez pop (N) w twojej odpowiedzi masz na myśli pop (k), N gdzie k jest pozycją elementu do usunięcia, a rozmiar wspomnianej tablicy to N. Wtedy k może być w zakresie od 0 do N-1, a więc na średnią N/2 operacje przesuwania elementów k + 1, ...., N-1 o jedną pozycję do tyłu. – ntg