Big O Notation | начин за сравняване на темповете на растеж на различни функции

В математиката и информатиката записът Big O е начин за сравняване на темповете на растеж на различни функции. Често се използва за сравняване на ефективността на различни алгоритми, което се прави чрез изчисляване на това колко памет е необходима и колко време е необходимо за изпълнение.

Записът "Голямо О" често се използва за определяне на сложността на даден проблем, известен също като клас на сложност на проблема. Математикът Паул Бакман (1837-1920) е първият, който използва тази нотация във второто издание на книгата си "Analytische Zahlentheorie" през 1896 г. Едмунд Ландау (1877-1938 г.) популяризира тази нотация. По тази причина, когато се говори за символи на Ландау, се има предвид тази нотация.

Нотацията Big O е кръстена на термина "ред на функцията", който се отнася до растежа на функциите. Записът Big O се използва за намиране на горната граница (най-високата възможна стойност) на темпа на растеж на функцията, което означава, че се изчислява най-дългото време, което ще е необходимо за превръщането на входа в изход. Това означава, че даден алгоритъм може да бъде групиран по това колко време може да отнеме в най-лошия случай, когато всеки път ще бъде избран най-дългият път.

По-конкретно, дадени са две положителни функции f ( x ) {\displaystyle f(x)} f(x) и g ( x ) {\displaystyle g(x)} $g(x)$ , казваме, че f {\displaystyle f} е в голямата О на g {\displaystyle g} (написано f ∈ O ( g ) {\displaystyle f\in O(g)} $f\in O(g)$ ), ако за достатъчно голямо x {\displaystyle x} , f ( x ) ≤ k ⋅ $f(x)\leq k\cdot g(x)$ за някаква константа k {\displaystyle k} .

Big O е израз, който намира времето за изпълнение в най-лошия случай, показвайки колко ефективен е даден алгоритъм, без да е необходимо програмата да се изпълнява на компютър. Това е полезно и поради факта, че различните компютри могат да имат различен хардуер и следователно да се нуждаят от различно време за изпълнение. Тъй като Big O винаги приема най-лошия сценарий, той може да покаже последователно измерване на скоростта: независимо от хардуера, O ( 1 ) {\displaystyle O(1)} $O(1)$ винаги ще завърши по-бързо от O ( n ! ) {\displaystyle O(n!)} $O(n!)$ , тъй като те имат различни нива на ефективност.

Примери

Всички следващи примери използват код, написан на Python. Имайте предвид, че това не е пълен списък на типовете Big O.

Постоянно

O ( 1 ) {\displaystyle O(1)} $O(1)$ винаги отнема едно и също време, независимо от входните данни. Например, вземете функция, която приема цяло число (наречено x) и връща двойната му стойност:

def double(x): return x * 2 #Връщане на стойността на x, умножена по 2

След като приеме входа, тази функция винаги прави една стъпка, за да върне изход. Тя е постоянна, защото винаги ще отнема едно и също време, така че е O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Линейна

O ( n ) {\displaystyle O(n)} $O(n)$ се увеличава в зависимост от размера на входа, представен с n {\displaystyle n} . Например, за следната функция, която приема n и връща всяко число от 1 до n:

def count(n): i = 1 #Създаване на брояч, наречен "i", със стойност 1 while i <= n: #Като i е по-малко или равно на n print(i) #Принтирайте стойността на i i = i + 1 #Предефинирайте i като "стойността на i + 1"

Ако въведем стойността 5, тогава ще се получи резултат $1,2,3,4,5$ , което изисква 5 цикъла за завършване. По същия начин, ако въведем стойност 100, тогава ще се изведе $1,2,3...98,99,100$ , което изисква завършването на 100 цикъла. Ако входът е n {\displaystyle n} , то времето за изпълнение на алгоритъма е точно n {\displaystyle n} цикъла всеки път, следователно е O ( n ) {\displaystyle O(n)} $O(n)$ .

Факториален

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ се увеличава във факторни числа, което означава, че времето, което отнема, се увеличава масово с входните данни. Например, да кажем, че искаме да посетим пет града по света и искаме да видим всяка възможна подредба (пермутация). Алгоритъмът, който бихме могли да напишем, използвайки библиотеката itertools на Python, е следният:

импортиране на itertools #Импортиране на библиотеката itertools cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Масив от избраните от нас градове def permutations(cities): #Приемане на масив от градове като вход: for i in itertools.permutations(cities): #За всяка пермутация на нашите елементи (зададена на променливата "i") print(i) #Изход i

Този алгоритъм ще изчисли всяка уникална пермутация на нашите градове и след това ще я изведе. Примерите за извеждане включват:

("Лондон", "Париж", "Берлин", "Амстердам", "Рим") ("Лондон", "Париж", "Берлин", "Рим", "Амстердам") ("Лондон", "Париж", "Амстердам", "Берлин", "Рим") ... ("Рим", "Амстердам", "Париж", "Берлин", "Лондон") ("Рим", "Амстердам", "Берлин", "Лондон", "Париж") ("Рим", "Амстердам", "Берлин", "Париж", "Лондон")

Тук нашият списък с входни данни е дълъг 5 елемента и за всеки избор оставащите ни възможности намаляват с 1. С други думи, нашите 5 входни данни избират $5\times 4\times 3\times 2\times 1$ елемента (или 5 ! {\displaystyle 5!} $5!$ ). Ако входът ни е дълъг n {\displaystyle n} града, тогава броят на изходите е n ! {\displaystyle n!} $n!$ ; като цяло, ако приемем, че преминаваме през всяка пермутация, тогава ще ни е необходимо O ( n ! ) {\displaystyle O(n!)} $O(n!)$ цикъла, за да я завършим.

Запис Little-o

Свързано с big-O запис понятие е little-o запис. Big-O се използва, за да се каже, че дадена функция не расте по-бързо от друга функция, докато little-o се използва, за да се каже, че дадена функция расте по-бавно от друга функция. Ако две функции растат с еднаква скорост, може да се използва big-O, но не и little-o. Разликата между big-O и little-o е подобна на разликата между ≤ {\displaystyle \leq } $\leq$ и < {\displaystyle <} $<$ .

Ако f ( x ) {\displaystyle f(x)} расте по-бавно от g ( x ) {\displaystyle g(x)} $g(x)$ , то f ( x ) ∈ $f(x)\in O(g(x))$ и f ( x ) ∈ $f(x)\in o(g(x))$ .
Ако f ( x ) {\displaystyle f(x)} расте със същата скорост като g ( x ) {\displaystyle g(x)} $g(x)$ , тогава f ( x ) ∈ $f(x)\in O(g(x))$ , но f ( x ) ∉ $f(x)\not \in o(g(x))$ .
Ако f ( x ) {\displaystyle f(x)} расте по-бързо от g ( x ) {\displaystyle g(x)} $g(x)$ , тогава f ( x ) ∉ $f(x)\not \in O(g(x))$ и f ( x ) ∉ $f(x)\not \in o(g(x))$ .

Въпроси и отговори

В: Какво представлява нотацията Big O?

О: Нотацията Big O е начин за сравняване на темповете на растеж на различни функции, често използван за сравняване на ефективността на различни алгоритми чрез изчисляване на това колко памет и време са необходими за изпълнение. Тя може да се използва и за определяне на това колко сложен е даден проблем.

Въпрос: Кой е първият, който е използвал този запис?

О: Математикът Паул Бахман (1837-1920 г.) е първият, който използва тази нотация в книгата си "Analytische Zahlentheorie" през 1896 г.

В: Какво означава Big O?

О: Big O означава "ред на функцията", който се отнася до скоростта на нарастване на функциите.

В: Как се използва Big O?

О: Записът Big O се използва за намиране на горна граница (най-високата възможна стойност) на скоростта на растеж на функцията, което означава, че се определя най-дългото време, което ще е необходимо за превръщането на входа в изход. Това означава, че алгоритмите могат да бъдат групирани по това колко време им отнема най-лошият сценарий, при който всеки път ще бъде избран най-дългият път.

В: Какво представляват символите на Ландау?

О: Символите на Ландау се отнасят до нотацията Big O, наречена на името на Едмънд Ландау (1877-1938 г.), който популяризира тази нотация.

В: Защо е полезен Big O?

О: Big O ни позволява да измерваме скоростта, без да се налага да стартираме програми на компютри, тъй като винаги предполага най-лошия сценарий, което я прави последователна, независимо от хардуерните разлики между компютрите. Той също така показва колко ефективен е даден алгоритъм, без да се налага да го изпълняваме на компютър.