Podcast
Questions and Answers
Која е конечната вредност на променливите a и b по извршување на задачата од денот 1?
Која е конечната вредност на променливите a и b по извршување на задачата од денот 1?
Што се случува ако низа s во функцијата first_non_repeating() не содржи незабележан знак?
Што се случува ако низа s во функцијата first_non_repeating() не содржи незабележан знак?
Каква е времевата сложеност на функцијата longest_increasing_subsequence()?
Каква е времевата сложеност на функцијата longest_increasing_subsequence()?
Што означува Θ (g(n))?
Што означува Θ (g(n))?
Signup and view all the answers
Која математичка операција е потребна за добивање на просечна времева сложеност во линеарно пребарување?
Која математичка операција е потребна за добивање на просечна времева сложеност во линеарно пребарување?
Signup and view all the answers
Кога е најпрактично да се користи Big Θ нотација?
Кога е најпрактично да се користи Big Θ нотација?
Signup and view all the answers
Што покажува сложеноста O(2^n)?
Што покажува сложеноста O(2^n)?
Signup and view all the answers
Која е конечната временска сложеност на линеарно пребарување ако клучот е отсутен во низата?
Која е конечната временска сложеност на линеарно пребарување ако клучот е отсутен во низата?
Signup and view all the answers
Што претставува Big-Omega Ω Notation?
Што претставува Big-Omega Ω Notation?
Signup and view all the answers
Кога се користи Big-Omega Ω Notation?
Кога се користи Big-Omega Ω Notation?
Signup and view all the answers
Каква е формалната дефиниција на Big-Omega?
Каква е формалната дефиниција на Big-Omega?
Signup and view all the answers
Што е првиот чекор во пресметувањето на Big-Omega?
Што е првиот чекор во пресметувањето на Big-Omega?
Signup and view all the answers
Кога ќе се отстраната константите при пресметувањето на Big-Omega?
Кога ќе се отстраната константите при пресметувањето на Big-Omega?
Signup and view all the answers
Кое од следниве функции е пример за Big-Omega?
Кое од следниве функции е пример за Big-Omega?
Signup and view all the answers
Која проширења на Big-Omega е точна кога се зборува за растот на алгоритмите?
Која проширења на Big-Omega е точна кога се зборува за растот на алгоритмите?
Signup and view all the answers
Која од следниве функции редовно расте побрзо од $n^2$ за големи вредности на n?
Која од следниве функции редовно расте побрзо од $n^2$ за големи вредности на n?
Signup and view all the answers
Study Notes
Алгоритми и Сложност
- Тема: Увод во 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
- Експоненцијална временска сложност поради рекурзивните повици.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Овој квиз ќе ви помогне да разберете основите на Дата Структури и Алгоритми (DSA) и сложностите на алгоритмите. Прашањата опфаќаат основни концепти, вклучувајќи работа со променливи, функции и нотации. Подгответе се за англиското веб учење и примена на вашите знаења во алгоритмите.
