Алгоритми и Сложност - Зимски 24/25

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

• Тема: Увод во DSA и Сложност
• Семестар: Зимски 24/25
• Предмет: Алгоритми и Сложност

Задача од ден 1

• Варијабли: a = 0, b = 0, N = 4, M = 4
• Циклус за итерација N пати: a = a + 10
• Циклус за итерација M пати: b = b + 40
• Испечатување на вредностите на a и b

Задача од ден 2

• Функција за пронаоѓање на првиот не-повторувачки карактер во стринг
• Број на појавувања на секој карактер се чува во речник
• Циклус низ стринг
• Ако карактерот веќе се наоѓа во речникот, го зголемува бројот на појавувања
• Инаку, го иницијализира на 1
• Втори циклус низ стринг
• Ако за даден карактер бројот на појавувања е 1, го враќа карактерот
• Инаку, враќа None

Задача од ден 3

• Функција за пронаоѓање на најдолгата возрастачки подниза
• dp = [1] * len(nums)
• За секој елемент во низата:
• За секој претходен елемент, ако е поголем, го зголемува dp[i]
• Враќа најголем елемент во dp

Дефиниција на голема тета (Θ) Нотација

• Θ(g(n)) = {f(n): постојат позитивни константи c1, c2 и n0 такви што 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) за сите n ≥ n0}

Експоненцијална временска сложност: голема О(2n) сложност

• Нотацијата го дава прецизното асимптотско ограничување
• Просечната временска сложност одразува реалистична перформанса
• f(n) останува во рамките на границите за големи n

Чекори за одредување на просечната временска сложност

• Разбиење на програмата на помали делови
• Наоѓање на сите видови и број на влезови и пресметување на бројот на операции
• Сите влезови треба да се рамномерно расподелат.
• Пресметување на збирот на сите изведени вредности и делење со вкупниот број на влезови
• Функцијата на n се претставува како g(n)
• Сложноста се означува како O(g(n)).

Пример

• Линеарно барање, просечната сложност е O(n)
• Пример на функција која ја следи линеарната сложност

Кога да се користи голема О (Θ) Нотација

• Кога е потребна прецизна анализа
• Подходяща за просечната временска сложност
• Има предизвици, бидејќи бара рамномерно распоредување на влезовите

Голема Омега (Ω) Нотација

• Asimptotno долен граница од временската сложност на алгоритмите
• Претставува минимален број на операции што се потребни за да се реши проблем со големина n

Како да се изчисли големата Омега

• Разбиете програмата на помали делови.
• Пронајдете ја сложноста на секој дел.
• Додајте ги сложностите на сите делови.
• Отстранете ги константите.
• Функцијата со најмала сложност која е пониска од f(n) е големата Омега (Ω).

Пример

• Линеарни функции, логаритамски функции, константи секогаш ќе растат побрзо од n^2

Голема О, Голема Омега, Голема Тета

• Голема О (O): Горна граница на сложност (најголема можна вредност)
• Голема Омега (Ω): Долна граница на сложност (најмала можна вредност)
• Голема Тета (Θ): Прецизно ограничување на сложноста
• Овие нотации можат да се користат за опишување на асимптотското однесување на алгоритми.

Вежби

• Наведени се неколку примери на алгоритми и нивната временска сложност (O)
• Наведени се примери на временски сложности за различни алгоритми (линеарно, бинарно барање, сортирање со мешање, вметнување, сортирање со мешање, и други)

Фабрицирање на Fibonacci

• Експоненцијална временска сложност поради рекурзивните повици.

Овој квиз ќе ви помогне да разберете основите на Дата Структури и Алгоритми (DSA) и сложностите на алгоритмите. Прашањата опфаќаат основни концепти, вклучувајќи работа со променливи, функции и нотации. Подгответе се за англиското веб учење и примена на вашите знаења во алгоритмите.