Big O Cheat Sheet: Обяснено с примери на Python

Big O Analysis е техника за анализиране и класиране на ефективността на алгоритмите.

Това ви позволява да изберете най-ефективните и мащабируеми алгоритми. Тази статия е Big O Cheat Sheet, обясняваща всичко, което трябва да знаете за Big O Notation.

Какво е Big O анализ?

Big O Analysis е техника за анализиране на това колко добре се мащабират алгоритмите. По-конкретно, ние питаме колко ефективен е даден алгоритъм, когато входният размер се увеличава.

Ефективността е колко добре се използват системните ресурси, докато се произвежда резултат. Ресурсите, които ни интересуват основно, са времето и паметта.

Следователно, когато извършваме Big O Analysis, въпросите, които задаваме, са:

Как се променя използването на памет от даден алгоритъм с нарастване на входния размер?

Как се променя времето, необходимо на алгоритъма, за да произведе изход, когато размерът на входа нараства?

Отговорът на първия въпрос е пространствената сложност на алгоритъма, докато отговорът на втория е неговата времева сложност. Използваме специална нотация, наречена Big O Notation, за да изразим отговорите и на двата въпроса. Това ще бъде разгледано по-нататък в Big O Cheat Sheet.

Предпоставки

Преди да продължа напред, трябва да кажа, че за да се възползвате максимално от този Big O Cheat Sheet, трябва да разберете малко алгебра. Освен това, тъй като ще давам примери за Python, също е полезно да разберете малко Python. Не е необходимо задълбочено разбиране, тъй като няма да пишете код.

Как да извършите голям O анализ

В този раздел ще разгледаме как да извършим Big O анализ.

Когато извършвате Big O Complexity Analysis, важно е да запомните, че ефективността на алгоритъма зависи от това как са структурирани входните данни.

Например, алгоритмите за сортиране работят най-бързо, когато данните в списъка вече са сортирани в правилния ред. Това е най-добрият сценарий за ефективността на алгоритъма. От друга страна, същите алгоритми за сортиране са най-бавни, когато данните са структурирани в обратен ред. Това е най-лошият сценарий.

Когато извършваме Big O Analysis, ние вземаме предвид само най-лошия сценарий.

Анализ на пространствената сложност

Нека започнем този Big O Cheat Sheet, като покрием как да извършим анализ на сложността на пространството. Искаме да разгледаме как допълнителната памет, която алгоритъмът използва, се мащабира, когато входът става все по-голям и по-голям.

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

def loop_recursively(n):
    if n == -1:
        return
    else:
        print(n)
        loop_recursively(n - 1)

По-доброто имплементиране обаче би изглеждало така:

def loop_normally(n):
    count = n
    while count >= 0:
        print(count)
        count =- 1

В алгоритъма по-горе създаваме само една допълнителна променлива и я използваме за цикъл. Ако n става все по-голямо и по-голямо, пак ще използваме само една допълнителна променлива. Следователно алгоритъмът има постоянна пространствена сложност, обозначена със символа „O(1)“.

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

Анализ на времевата сложност

Когато извършваме анализ на времевата сложност, не сме загрижени за нарастването на общото време, заето от алгоритъма. По-скоро сме загрижени от нарастването на предприетите изчислителни стъпки. Това е така, защото действителното време зависи от много системни и случайни фактори, които трудно могат да бъдат отчетени. Така че ние проследяваме само растежа на изчислителните стъпки и приемаме, че всяка стъпка е равна.

За да демонстрирате анализа на времевата сложност, разгледайте следния пример:

Да предположим, че имаме списък с потребители, където всеки потребител има ID и име. Нашата задача е да внедрим функция, която връща името на потребителя, когато му бъде даден ID. Ето как можем да направим това:

users = [
    {'id': 0, 'name': 'Alice'},
    {'id': 1, 'name': 'Bob'},
    {'id': 2, 'name': 'Charlie'},
]

def get_username(id, users):
    for user in users:
        if user['id'] == id:
            return user['name']
    return 'User not found'

get_username(1, users)

Имайки списък с потребители, нашият алгоритъм преминава през целия потребителски масив, за да намери потребителя с правилния идентификатор. Когато имаме 3 потребители, алгоритъмът изпълнява 3 итерации. Когато имаме 10, той изпълнява 10.

Следователно броят на стъпките е линейно и право пропорционален на броя на потребителите. И така, нашият алгоритъм има линейна времева сложност. Въпреки това можем да подобрим нашия алгоритъм.

Да предположим, че вместо да съхраняваме потребителите в списък, ги съхраняваме в речник. Тогава нашият алгоритъм за търсене на потребител ще изглежда така:

users = {
    '0': 'Alice',
    '1': 'Bob',
    '2': 'Charlie'
}

def get_username(id, users):
     if id in users:
         return users[id]
     else:
         return 'User not found'

get_username(1, users)

С този нов алгоритъм, да предположим, че имаме 3 потребители в нашия речник; ще извършим няколко стъпки, за да получим потребителското име. И да предположим, че имаме повече потребители, да речем десет. Ще изпълним същия брой стъпки, както преди, за да получим потребителя. С нарастването на броя на потребителите броят на стъпките за получаване на потребителско име остава постоянен.

Следователно този нов алгоритъм има постоянна сложност. Няма значение колко потребители имаме; броят на предприетите изчислителни стъпки е същият.

Какво е Big O Notation?

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

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

Линейната сложност е представена с n, така че бихме го написали като O(n) (да се чете като „O of n“). Постоянната сложност е представена с 1, така че ще я запишем като O(1).

Има още сложности, които ще обсъдим в следващия раздел. Но като цяло, за да напишете сложност на алгоритъм, следвайте следните стъпки:

Опитайте се да разработите математическа функция на n, f(n), където f(n) е количеството използвано пространство или изчислителните стъпки, последвани от алгоритъма, а n е входният размер.

Вземете най-доминиращия термин в тази функция. Редът на доминиране на различните термини от най-доминиращия до най-малко доминиращия е както следва: Факториален, Експоненциален, Полиномен, Квадратичен, Линеаритмичен, Линеен, Логаритмичен и Константен.

Елиминирайте всички коефициенти от термина.

Резултатът от това става терминът, който използваме в нашите скоби.

Пример:

Помислете за следната функция на Python:

users = [
    'Alice',
    'Bob',
    'Charlie'
]

def print_users(users):
    number_of_users = len(users)
    print("Total number of users:", number_of_users)

    for i in number_of_users:
        print(i, end=': ')
        print(user)

Сега ще изчислим сложността на Big O Time на алгоритъма.

Първо пишем математическа функция на nf(n), за да представим броя на изчислителните стъпки, които алгоритъмът предприема. Спомнете си, че n представлява входния размер.

От нашия код функцията изпълнява две стъпки: едната за изчисляване на броя на потребителите, а другата за отпечатване на броя на потребителите. След това за всеки потребител той изпълнява две стъпки: една за отпечатване на индекса и една за отпечатване на потребителя.

Следователно функцията, която най-добре представя броя на предприетите изчислителни стъпки, може да бъде записана като f(n) = 2 + 2n. Където n е броят на потребителите.

Преминавайки към втора стъпка, избираме най-доминиращия термин. 2n е линеен член, а 2 е постоянен член. Линейният е по-доминиращ от константата, така че избираме 2n, линейният член.

И така, нашата функция сега е f(n) = 2n.

Последната стъпка е премахването на коефициентите. В нашата функция имаме 2 като наш коефициент. Така че го елиминираме. И функцията става f(n) = n. Това е терминът, който използваме между нашите скоби.

Следователно времевата сложност на нашия алгоритъм е O(n) или линейна сложност.

Различни големи O сложности

Последният раздел в нашия Big O Cheat Sheet ще ви покаже различни сложности и свързаните с тях графики.

#1. Константа

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

Постоянната сложност е представена като O(1). Въпреки това, не винаги е възможно да се напишат алгоритми, които работят с постоянна сложност.

#2. Логаритмичен

Логаритмичната сложност е представена от термина O(log n). Важно е да се отбележи, че ако основата на логаритъм не е посочена в Computer Science, приемаме, че е 2.

Следователно log n е log2n. Известно е, че логаритмичните функции първо растат бързо и след това се забавят. Това означава, че те мащабират и работят ефективно с все по-голям брой n.

#3. Линеен

За линейни функции, ако независимата променлива се мащабира с коефициент p. Зависимата променлива се мащабира със същия фактор p.

Следователно функция с линейна сложност нараства със същия коефициент като входния размер. Ако размерът на входа се удвои, броят на изчислителните стъпки или използването на паметта ще се удвои. Линейната сложност се представя със символа O(n).

#4. Линеаритмичен

O (n * log n) представлява линейни функции. Линеаритмичните функции са линейна функция, умножена по функцията логаритъм. Следователно линейна функция дава резултати, малко по-големи от линейните функции, когато log n е по-голямо от 1. Това е така, защото n се увеличава, когато се умножи по число, по-голямо от 1.

Log n е по-голямо от 1 за всички стойности на n, по-големи от 2 (не забравяйте, че log n е log2n). Следователно, за всяка стойност на n, по-голяма от 2, линейните функции са по-малко мащабируеми от линейните функции. От които n е по-голямо от 2 в повечето случаи. Така че линейните функции обикновено са по-малко мащабируеми от логаритмичните функции.

#5. Квадратичен

Квадратичната сложност е представена от O(n2). Това означава, че ако размерът на вашия вход се увеличи 10 пъти, броят на предприетите стъпки или използваното пространство се увеличава 102 пъти или 100! Това не е много мащабируемо и както можете да видите от графиката, сложността нараства много бързо.

Квадратичната сложност възниква в алгоритми, при които зацикляте n пъти и за всяка итерация отново зацикляте n пъти, например при Bubble Sort. Въпреки че като цяло не е идеален, понякога нямате друг избор, освен да прилагате алгоритми с квадратична сложност.

#6. Полином

Алгоритъм с полиномиална сложност се представя с O(np), където p е някакво постоянно цяло число. P представлява реда, в който n се повишава.

Тази сложност възниква, когато имате ap брой вложени цикли. Разликата между полиномна сложност и квадратична сложност е, че квадратичната е от порядъка на 2, докато полиномът има всяко число, по-голямо от 2.

#7. Експоненциален

Експоненциалната сложност расте дори по-бързо от полиномната сложност. В математиката стойността по подразбиране за експоненциалната функция е константата e (числото на Ойлер). В компютърните науки обаче стойността по подразбиране за експоненциалната функция е 2.

Експоненциалната сложност е представена със символа O(2n). Когато n е 0, 2n е 1. Но когато n се увеличи до 5, 2n нараства до 32. Увеличаването на n с единица ще удвои предишното число. Следователно експоненциалните функции не са много мащабируеми.

#8. Факториал

Факторната сложност е представена със символа O(n!). Тази функция също се разраства много бързо и следователно не може да се мащабира.

Заключение

Тази статия разглеждаше анализа на Big O и как да го изчислим. Обсъдихме също различните сложности и обсъдихме тяхната мащабируемост.

След това може да искате да практикувате Big O анализ на алгоритъма за сортиране на Python.