AlegsaOnline.com

Big O (Голямо O) нотация — дефиниция, примери и анализ на сложността

Научете Big O (Голямо O) нотация: дефиниция, примери и анализ на сложността на алгоритми — ясни обяснения, примери и съвети за оптимизация.

Автор: Leandro Alegsa Дата на създаване: 20 май 2021 г. Последна актуализация: 10 ноември 2025 г.

В математиката и информатиката записът Big O (наричан още Голямо O) описва как се увеличава една функция при нарастване на аргумента ѝ. На практика това служи за сравняване на темповете на растеж на различни функции и за оценка на ефективността на алгоритми — колко памет и колко време са необходими за изпълнение спрямо размера на входа.

Исторически, нотацията идва от работите в теория на числата: Паул Бахман (Paul Bachmann, 1837–1920) използва подобни означения в по-ранни издания, а Едмунд Ландау (Edmund Landau, 1877–1938) популяризира тази форма на изразяване. Поради това често се среща и терминът "символи на Ландау".

Какво точно означава Big O?

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

Формално определение

За две положителни функции 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} .

На по-прост език: f(x) е O(g(x)), ако за всички достатъчно големи x стойността на f(x) не надвишава някаква константа, умножена по g(x). Това означава, че g(x) отговаря за "темпа на растеж" на f(x) (до постоянен коефициент).

Често срещани класове сложност

O(1) — константно време: изпълнението не зависи от размера на входа (например достъп до елемент в масив по индекс).
O(log n) — логаритмично време: пример е двоично търсене.
O(n) — линейно време: една обиколка през всички елементи на масив.
O(n log n) — например бързи сортиращи алгоритми като quicksort и mergesort (в среден/добрия случай).
O(n^2) — квадратично време: вложени двойни цикли (например прост сортиращ алгоритъм като bubble sort).
O(2^n) — експоненциално време: обикновено при проблеми с избиране на подмножества, като решаване на задачи чрез брутално изброяване.
O(n!) — факториално време: пример е генериране на всички пермутации на n елемента.

Примери в код (интуиция)

Едно присвояване или условна проверка: O(1).
Цикъл, който преминава веднъж през n елемента: O(n).
Два вложени цикъла, всеки от n итерации: O(n^2).
Двоично търсене в сортиран масив: O(log n).

Най-лош, среден и най-добър случай; пространство

Big O обикновено описва най-лошия случай (worst-case). Има и други нотации: Θ (Theta) описва точна асимптотична граница (горна и долна), а Ω (Omega) — долна граница (best-case). Освен времева сложност, говорим и за пространствена сложност (колко допълнителна памет използва алгоритъмът), която се анализира по същия начин с Big O.

Защо Big O е полезна

Позволява да се сравняват алгоритми независимо от конкретната машина или език за програмиране.
Фокусира се върху поведението при големи входни размери — най-важното при мащабируеми системи.
Помага да се откроят алгоритми, които стават неприложими при растеж на данните (напр. факториални или експоненциални сложностите).

Практически съвети

При малки n константните фактори и оптимизациите могат да са по-важни; при големи n асимптотичната сложност доминира.
Опитайте да намалите степента на n (например от n^2 към n log n или n) — това обикновено дава най-голямо подобрение.
Анализирайте както времето, така и паметта, защото спестяването на време често увеличава използваната памет и обратно.

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

Примери

Всички следващи примери използват код, написан на 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 ни позволява да измерваме скоростта, без да се налага да стартираме програми на компютри, тъй като винаги предполага най-лошия сценарий, което я прави последователна, независимо от хардуерните разлики между компютрите. Той също така показва колко ефективен е даден алгоритъм, без да се налага да го изпълняваме на компютър.

Автор

AlegsaOnline.com - Big O Notation - Leandro Alegsa

Дата на създаване: 20 май 2021 г.
Последна актуализация: 10 ноември 2025 г.

URL: https://bg.alegsaonline.com/art/11364