sem_02

Упражнение 2

Сложност на алгоритми

Миналия път разгледахме

• Защо е важно СДА-то?
• HackerRank демо
• Обектите в Python
• Bigint
• List comprehension
• GIL (Global Interpreter Lock)

Днес ще разгледаме

• Видове сложности
• Правила за смятане на Big O изрази
• Основи при изчисляване на сложности

Въпроси от миналия път

• copy() vs deepcopy()
• using filter()

Copy vs Deepcopy

Присвояване на стойността на масив чрез оператор =, без използването на copy(). Промени в бащата/ детето, водят до промени и в бащата, и в детето:

father = [i for i in range(5)]
child = father

father.insert(2, 99) # same with child.insert()

print("Father: ", father)   # [0, 1, 99, 2, 3, 4]
print("Child: ", child)     # [0, 1, 99, 2, 3, 4]

Родителят и детето са един и същи обект:

print(id(child) == id(father) # True

---

Копиране на масив чрез метода copy(). Промени в бащата не се отразяват на промени в детето. Обратното също е вярно.

father = [i for i in range(5)]
child = father.copy()

father.insert(2, 99)

print("Father: ", father)   # [0, 1, 99, 2, 3, 4]
print("Child: ", child)     # [0, 1, 2, 3, 4]

Родителят и детето са два различни обекта:

print(id(child) != id(father) # True

---

Копиране на масив, съдържащ съставни обекти (масив от mutable objects) чрез използване на метод copy(). Промени в съставен обект на бащата водят до промени и в детето.

from copy import copy

inner_list = [4, 5]

father = [1, 2, 3, inner_list]
child = copy(father)

father[3].append(6) # equals inner_list.append(6)

print("Father: ", father)   # [1, 2, 3, [4, 5, 6]]
print("Child: ", child)     # [1, 2, 3, [4, 5, 6]]

Детето и бащата са два различни обекта, но съставните части си остават същите при използването на copy().

print(id(child) != id(father)) # True
print(id(child[3]) == id(father[3])) # True

---

Копиране на масив, съдържащ съставни обекти (масив от mutable objects) чрез използване на метод deepcopy(). Промени в съставен обект на бащата не водят до промени в детето.

from copy import deepcopy

inner_list = [4, 5]

father = [1, 2, 3, inner_list]
child = deepcopy(father)

father[3].append(6)

print("Father: ", father)   # [1, 2, 3, [4, 5, 6]]
print("Child: ", child)     # [1, 2, 3, [4, 5]

Детето и бащата са два различни обекта, и съставните части са различни обекти при използването на deepcopy().

print(id(child) != id(father)) # True
print(id(child[3]) == id(father[3])) # True

Filter()

Filter() се нуждае от аргумент функция, по която да се извърши филтрирането. (В Python функциите притежават способността да бъдат подавани, като аргумент на функция - First-class citizen)

Това може да е наша дефинирана функция:

arr = [i for i in range(10)]

def check_if_even(x):
    return x % 2 == 0

even_arr = list(filter(check_if_even, arr))
print(even_arr) # [0, 2, 4, 6, 8]

Или може да е анонимна функция, така наречените ламбда изрази:

arr = [i for i in range(10)]

even_arr = list(filter(lambda x: x % 2 == 0, arr))
print(even_arr) # [0, 2, 4, 6, 8]

Видове сложности:

• константа - O(1)
• логаритмична - О(logN)
• линейна - O(N)
• енлог - O(NlogN)
• квадратична - O(N²)
• кубична - O(N³)
• експоненциална - O(c^N)

Ред на нарастване на времето:

1 < logN < sqrtN < N < NlogN < N² < N³ < 2^N < 3^N < N! < N^N

Правила за смятане на Big O изрази:

• константите, които са множители не влияят.

  O(100N) = O(N)

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

  О(N² + NlogN + N + 1) = O(N²)

• при произведение от множители, влияят всички функции.

  *O(N² log³N) не може да бъде опростено.

• основата на логаритъма не влияе.

  O(log₂N) = O(log₃N)

  Изписва се просто O(logN). Това не важи за степента на логаритмична функция (горния пример).

---

Примери:

• О(2N) = O(N) = O(10000N)
• O(10000000) < O(logN)
• O(N + M)

При невъзможност да се определи коя функция е по-голяма N или М, изразът O(N + M) не може да бъде опростен.

Колко разлика оказва сложността? (практичен пример)

Нека имаме 2 компютъра. Компютър А е най-бързият за времето си със производителност 10 милиарда операции в секунда. Компютър Б е обикновен компютър и изчислява 10 милиона операции в секунда.

Задачата на компютрите е да сортират масив с 10 милиона елемента.

Машина А използва Insertion sort със сложност 2N². Машина Б използва Мerge sort със сложност 50NlogN.

За колко време всяка машина ще се справи със задачата?

Суперкомпютър А:

• S₁ = 2N² стъпки, за N = 10⁷
• V₁ = 10¹⁰ стъпки/ сек
• => t₁ = 20000 сек. = ~5.5 ч.

Компютър Б:

• S₂ = 50NlogN стъпки, за N = 10⁷
• V₂ = 10⁷ стъпки/ сек
• => t₂ = ~1163 сек. = ~20 мин.

Въпреки разликата в производителността и константите в алгоритмите (2 и 50), резултатите са коренно различни.

Още по-съществена разлика се наблюдава при увеличаване на големината на масива 10 пъти. При N = 100 милиона числа, компютър А отнема 23 дни, а компютър Б - 4 часа.

Основи при изчисляване на сложности

O(1) - връщането на константа:

def get_Pi():
    return 3.14

O(1) - връщането на елемент от масив:

def get_5th_element(arr):
    return arr[5]

---

O(N) - еднократно обхождане на масив с големина N.

for el in arr:
    print(el)

O(N²) - обхождане на масив с големина N N пъти (чрез вложен цикъл). Обхождане на матрица с размер NxN.

for i in range(N):
    for j in range(N):
        print(i, j)

---

O(2^N) - Намиране на N-тото число от редицата на Фибоначи. Всяко извикване на функцията, създава 2 нови деца, всяко от които 2 свои деца и т.н.

def fibonacci(N):
    if N <= 1:
        return N
    return fibonacci(N-1) + fibonacci(N-2)

O(logN) - Намиране на колко двойки се съдържат в числото N. На всяко рекурсивно извикване, числото намаля 2 пъти.

def count_deuces(N, count = 0):
    if N <= 1:
        return count
    
    count += 1
    return count_deuces(N // 2, count)

---

O(N + M) - обхождане на масив с големина N и масив с големина M.

def brothers(N, M):
    for i in range(N):
        print(i)

    for j in range(M):
        print(j)

Задачи за упражнение (в LeetCode)

• Move Zeroes
• Two Sum
• Plus One
• Rotate Image

Решения на задачите: тук