AlegsaOnline.com

Asymptotyczne tempo wzrostu

Autor: Leandro Alegsa

17-12-2020

Big O Notation to sposób na porównanie algorytmów. Porównuje je poprzez obliczenie, ile pamięci potrzeba i ile czasu potrzeba na ich wykonanie.

Notacja Big O jest często używana w celu określenia, jak skomplikowany jest problem, znany również jako klasa złożoności problemu. Matematyk Paul Bachmann (1837-1920) jako pierwszy użył tego zapisu w drugim wydaniu swojej książki "Analytische Zahlentheorie" w 1896 roku. Edmund Landau (1877-1938) uczynił ten zapis popularnym. Z tego powodu, gdy ludzie mówią o symbolach Landaua, odwołują się do tego zapisu.

Nazwa Big O Notation pochodzi od terminu "kolejność funkcji", który odnosi się do wzrostu funkcji. Big O Notation jest używany do znalezienia górnej granicy (największej możliwej wielkości) tempa wzrostu funkcji, co oznacza, że pracuje on najdłużej, jak długo potrwa przekształcenie wejścia w wyjście. Oznacza to, że algorytm może być pogrupowany według czasu, jaki może upłynąć w najgorszym przypadku, gdy za każdym razem najdłuższa trasa zostanie pokonana.

Duże O to wyrażenie, które znajduje najgorszy scenariusz działania, pokazujące jak wydajny jest algorytm bez konieczności uruchamiania programu na komputerze. Jest to również użyteczne, ponieważ różne komputery mogą mieć różny sprzęt i dlatego potrzebują różnej ilości czasu na jego wykonanie. Ponieważ Big O zawsze zakłada najgorszy scenariusz, może pokazać spójny pomiar prędkości: niezależnie od sprzętu, O ( 1 ) {\i1} {\i1}displaystyle O(1)} $O(1)$ zawsze będzie ukończony szybciej niż O ( n ! ) {\i1}displaystyle O(n !)} $O(n!)$ ponieważ mają różne poziomy wydajności.

Przykłady

W poniższych przykładach wszyscy używają kodu napisanego w Pythonie. Zauważ, że nie jest to pełna lista typów Big O.

Stały

O ( 1 ) {\i1}Style O(1)} $O(1)$ . Zawsze zajmuje tyle samo czasu bez względu na wejście. Na przykład, weź funkcję, która przyjmuje liczbę całkowitą (zwaną x) i zwraca podwójną jej wartość:

def double(x): return x * 2 #Wróć wartość x razy 2

Po zaakceptowaniu wejścia, funkcja ta zawsze podejmie jeden krok w celu zwrócenia wyjścia. Jest ona stała, ponieważ zawsze będzie trwała tak samo bez przerwy, więc jest to O ( 1 ) {\i1}styla O(1)} $O(1)$ .

Linear

O ( n ) {\i1}Style O(n)} $O(n)$ . Zwiększa się w zależności od wielkości wejścia, reprezentowanego przez n {\i1}styk n{\i0} . Załóżmy, że funkcja przyjmuje n, i zwraca każdą liczbę od 1 do n:

def count(n): i = 1 #Utwórz licznik zwany "i" o wartości 1, a i <= n: #Podczas gdy i jest mniejsze lub równe n print(i) #Drukuj wartość i i = i + 1 #Zdefiniuj i jako "wartość i + 1"

Gdybyśmy mieli wprowadzić wartość 5, to wypisalibyśmy 1 , 2 , 3 , 4 , 5 {\i1,2,3,4,5} $1,2,3,4,5$ wymaga 5 pętli do wykonania. Podobnie, jeśli wprowadzimy 100, wyjdzie 1, 2, 3...98, 99, 100...98, 99, 100...98, 99, 100 $1,2,3...98,99,100$ , wymagając 100 pętli do wykonania. Jeśli wejściem jest n {\i1}styk n{\i1} to czas działania algorytmu jest dokładnie n {\i1}pętli za każdym razem, więc jest to O ( n ) {\i1} {\i1}styk O(n)} $O(n)$ .

Factorial

O ( n ! ) {\i1}Style O(n !)} $O(n!)$ . Zwiększa się ilość czynnika, co oznacza, że czas potrzebny na jego wprowadzenie ogromnie się wydłuża. Na przykład, powiedzmy, że chcemy odwiedzić pięć miast na całym świecie i chcemy zobaczyć każde możliwe zamówienie (permutację). Algorytm, który moglibyśmy napisać korzystając z biblioteki itertools Pythona, jest następujący:

import itertools #Import the itertools library cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Matka naszych wybranych miast def permutations(miast): #Taking an array of cities as input: for i in itertools. permutations(cities). [permutations(cities)] = ['Londyn', 'Paryż', 'Berlin', 'Rzym] #Dla każdej permutacji naszych pozycji (przypisanej do zmiennej "i") print(i) #Output i

Ten algorytm obliczy każdą unikalną permutację naszych miast, a następnie wypuści ją na zewnątrz. Przykładowe dane wyjściowe będą zawierać:

("Londyn", "Paryż", "Berlin", "Amsterdam", "Rzym") ("Londyn", "Paryż", "Berlin", "Rzym", "Amsterdam") ("Londyn", "Paryż", "Amsterdam", "Berlin", "Rzym") ... ("Rzym", "Amsterdam", "Paryż", "Berlin", "Londyn") ("Rzym", "Amsterdam", "Berlin", "Londyn", "Paryż") ("Rzym", "Amsterdam", "Berlin", "Paryż", "Londyn")

Tutaj nasza lista wejść jest długa na 5 pozycji, a dla każdego wyboru pozostałe opcje zmniejszają się o 1. Innymi słowy nasze 5 wejść wybieramy 5 × 4 × 3 × 2 × 1 {\i0}styk 5 × 4 × 3 × 2 × 1}pozycji (lub $5\times 4\times 3\times 2\times 1$ 5 ! {\i0}styk 5!} $5!$ ). Jeżeli nasze wejście jest n miast długi, to liczba wyjść wynosi n! Innymi słowy, zakładając, że przejdziemy przez każdą permutację wymagającą O ( n ! ) $n!$ $O(n!)$ pętli O ( n ! ) aby to zakończyć.

Little-o Notacja

Surowsza wersja Wielkiego O jest mała-o. Różnica między dużym O a małym-o jest taka, że little-o jest ścisłym górnym ograniczeniem: podczas gdy O ( n ) {\i1}displaystyle O(n)} $O(n)$ oznacza, że czas ukończenia zwiększy się do tego maksimum w oparciu o wielkość wejścia, o ( n ) {\i1}displaystyle o(n)} $o(n)$ oznacza, że czas ukończenia będzie generalnie poniżej tego czasu. Innymi słowy, Big O zakłada, że każda pętla przyjmie najdłuższą ścieżkę i proces będzie trwał jak najdłużej, podczas gdy little-o jest bardziej realistyczne w odniesieniu do rzeczywistych czasów przebiegu; jeśli liczba pętli jest oparta na rzucie sześciokątnym Big O zawsze zakłada, że rzucana jest szóstka, podczas gdy little-o bierze pod uwagę równe prawdopodobieństwo, że inne liczby są rzucane.

Pytania i odpowiedzi

P: Co to jest notacja Big O?

O: Notacja Big O to sposób porównywania tempa wzrostu różnych funkcji, często wykorzystywany do porównywania efektywności różnych algorytmów poprzez obliczanie, ile pamięci i czasu zajmuje wykonanie zadania. Można ją również wykorzystać do określenia stopnia złożoności problemu.

P: Kto jako pierwszy użył tej notacji?

O: Matematyk Paul Bachmann (1837-1920) jako pierwszy użył tej notacji w swojej książce "Analytische Zahlentheorie" w 1896 roku.

P: Co oznacza duże O?

O: Duże O oznacza "rząd funkcji", który odnosi się do szybkości wzrostu funkcji.

P: Jak używa się Big O?

O: Notacja Big O służy do znalezienia górnej granicy (największej możliwej wielkości) tempa wzrostu funkcji, co oznacza, że określa najdłuższy czas, w jakim dane wejściowe zostaną zamienione w dane wyjściowe. Oznacza to, że algorytmy można pogrupować według tego, ile czasu zajmują w najgorszych scenariuszach, gdzie za każdym razem wybierana jest najdłuższa droga.

P: Co to są symbole Landaua?

O: Symbole Landaua odnoszą się do notacji Big O, nazwanej tak na cześć Edmunda Landaua (1877-1938), który spopularyzował tę notację.

P: Dlaczego Big O jest przydatne?

O: Big O pozwala nam mierzyć szybkość działania bez konieczności uruchamiania programów na komputerach, ponieważ zawsze zakłada najgorsze scenariusze, dzięki czemu jest spójny bez względu na różnice sprzętowe między komputerami. Pokazuje również, jak wydajny jest algorytm bez konieczności uruchamiania go na komputerze.