NEW
Font size
Worksheetsалгоритм 1-40
Total questions: 40
Worksheet time: 20mins
Алгоритмнің күрделілігі … өлшенеді
кірістегі мәліметтердің санымен
бір уақыт бірлігіндегі операция санымен
оперативты жадының көлемімен
тұрақты жады көлемімен
Алгоритмның асимптотикалық күрделілігі
Бағдарламалау тілі, мәліметтердің типі, процессор түріне, т.б
оперативты жадының көлемімен
Уақыттық күрделілік алгоритмнің тиімділігін көрсетеді, әдетте O(n)O(n)O(n), O(n2)O(n^2)O(n2), O(logn)O(\log n)O(logn) сияқты үлкен О нотациясымен өлшенеді
мәліметтердің санымен
Есептің орындалу уақыты
Есептің орындалу уақыты және Жадыны тиімді пайдалану
Уақыттық күрделілік алгоритмнің тиімділігін көрсетеді, әдетте O(n)O(n)O(n), O(n2)O(n^2)O(n2), O(logn)O(\log n)O(logn) сияқты үлкен О нотациясымен өлшенеді.
Бағдарламалау тілі, мәліметтердің типі, процессор түріне, т.б
Алгоритмдердің күрделілігі
4
Big (үлкен) О (О – нотация) арқылы белгіленеді
2
Есептің орындалу уақыты және Жадыны тиімді пайдалану
жағдайдың ең нашар нұсқасын көрсетеді немесе жоғарғы шекарасын
O(n1
Big (үлкен) О (О – нотация) арқылы белгіленеді
O(n)
O(2
10 элементтен тұратын массивтың бірінші элементі мен соңғы элемнтінің қосындысын көрсету.
val nums = intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11)
val sumNumber = nums[0] + nums[9]. Есептегі операция саны
1
2
0
4
5 элементтен тұратын массивтың бірінші элементын көрсету.
Бұл жерде кірістегі деректерді қанша көбейтседе (100, 1000, 10 000 элемент) мұнда бір ғана операция орындалады
val firstNumber = nums[0]
val nums = intArrayOf (1, 2, 3, 4, 5)
алгоритмның күрделілігін анықта.
O(1)
O(n)
O(2)
O(
Сызықты функция
fun pairSumSequence(n: Int): int {
var sum = 0
for (i in 0 until n) {
sum += pairSum(i, i + 1)
}
return sum
}
fun pairSum(a: Int, b: int) = a + b
1 дурыс
Алгоритмның күрделілігін анықта.
O(1)
O(2)
O(n)1
O(n)
Рекурсивті функция
fun sum(n: int): int {
if (n == 1) return 1
return n + sum(n - 1)
}
1 дурыс
O(n) - қолданады
нейрондық желіде
алгоритмнің қасиетіне бағалауда
алгоритмдардың күрделілігін бағалауда
математикалық статистикады
Сызықты іздеуде орташа және нашар уақыттық күрделілік
>O(|V||E|), O(|V||E|)
O(|V|2), O(|V|2)
О(n), О(n)
O(log(n)), O(log(n)),
<question>Массивті басымдықты кезек ретінде қолданып Дейкстр алгоритмі арқылы ең қысқа жолды іздеудегі орташа және нашар уақыттық күрделілік
O(|V|2), O(|V|2)
O(|E|+|V|)
O(log(n)), O(log(n)),
O((|V|+|E|)log|V|), O((|V|+|E|)log|V|)
Тереңге (DFS) және еніне (BFS) іздеудегі орташа және нашар уақыттық күрделілік
O(|V|2), O(|V|2)
O(log(n)), O(log(n)),
O(|E|+|V|)
О(n), О(n)
Жылдам сұрыптаудағы ең жақсы, орташа және нашар уақыттық күрделілік
O(n log(n)), O(n log(n)), О(n2)
О(n), О(n2), О(n2)
O(log(n)), O(log(n))
O(nk),O(nk),O(nk)
Деректердің құрылымына не жатпайды
тізім, граф
статикалық массив
кезек
хеш кесте
Деректердің абстракты типі
байланысқан тізім
тізім, кезек
тізбек
статикалық массив
Деректердің сызықты типі
екіжақты және басты енуімен
параллельді және тізбекті енуімен
тура және тізбекті енуімен
біржақты және соңғы енуімен
Элементтерді кірістіру (PUSH) және жою (POP) жоғарғы жағынан (top) жүзеге асырылатын тізім тәрізді деректердің абстрактілі типі
стек (stack)
дек (deque)
кезек (queue)
жиын (set)
Кез келген жерден элементтерді жояды және кірістіреді. Бір типті элементтердің мәні (value) мен индекстер (index) жиының сақтайтын деректердің абстрактілі типі
тізім (list)
тізі (list)
дек (deque)
кезек (queue)
Кірістіру соңынан (tail, rear, back), ал жою алдынан жүзеге асырылатын тізім тәрізді деректердің абстрактілі типі. «Бірінші келдін – бірінші кеттің» принципімен жұмыс жасайлы.
жиын (set)
тізім (list)
дек (deque)
кезек (queue)
Бір типтегі элементтердің жиыны. Элементтірді жою, қосу, іздеу функцияларын сүйемелдейді. Осы деректер абстрактілі типі негізінде ассоциативті массивтер (сөздіктер) және басымдықты тізім фундаменталдық деректер типтері іске асырылады
жиын (set)
кезек (queue)
тізім (list)
стек (stack)
Төбелер (vertices) және оларды байланыстырған қабырғаларынан (edges) тұратын деректердің абстрактілі типі
граф (graph)
тізім (list)
кезек (queue)
дек (deque)
Денесінде өз өзін шақыру амалы бар функция
іздеу
шарт
цикл
рекурсия
1.Егер есеп үлкен болса, онда оны ішкі бөліктерге бөлу керек 2. Ішкі бөліктерге рекурсия қолданып, ал егер кішкентай болса тікелей шешу керек 3. 1-ші мен 2-ші бөліктің комбинациясы
соңғы келіп, соңғы кетті»
Бөлде билік жүргіз»
бірінші келіп, бірінші кетті»
төменнен жоғарыға қарай шешу»
Берілген n элементтен тұратын тізбекті реттеу
сұрыптау
іздеу
жою
жаңарту
Бірігу арқылы сұрыптау (merge sort) әдісіне негізделген…
салыстыру бойынша элементтердін орнын ауыстыру
екі бөлікке бөлу
Бөлде билік жүргіз»
сандардың разряды бойынша салыстыру
Бірігу арқылы сұрыптау (merge sort) әдісіне негізделген…
салыстыру бойынша элементтердін орнын ауыстыру
екі бөлікке бөлу
Бөлде билік жүргіз»
сандардың разряды бойынша салыстыру
Жылдам сұрыптау немесе Хоара (Quick-sort) әдісі
ең үлкен элемент массивтің соңына орналасады
сандардың разряды бойынша салыстыру
тірек элементіне негізделіп екі бөлікке бөлу
«бөлде билік жүргіз»
Кірістру арқылы сұрыптау (Insertion-sort)
екі бөлікке бөлу
ең үлкен элемент массивтің соңына орналасады
бөлде билік жүргіз»
элементті салыстыру және керекті позицияға кірістіру
Алмастыру арқылы сұрыптау (Bubble-sort) немесе көпіршік сұрыптау
массивтің ең үлкен элементің тізімнің соңына орналастырады
бөлде биле»
екі бөлікке бөлу
сандардың разряды бойынша салыстыру
Цифрлық сұрыптау – рязряд бойынша (Radix-Sort)
элементті салыстыру және керекті позицияға кірістіру
ең үлкен элемент массивтің соңына орналасады
сандардың разряды бойынша салыстыру
бөлде билік жүргіз»
Шелл (Shell Sort) сұрыптауы
екі бөлікке бөлу
элементті салыстыру және керекті позицияға кірістіру
ең үлкен элемент массивтің соңына орналасады
массив екі элементтен бірнеше бөлікке бөлінеді
Үйінді сұрыптауы ол
пирамидалық сұрыптау
жылдам сұрыптау
көпіршікті сұрыптау
кірістіру арқылысұрыптау
Циклсыз байланысқан граф
Стек
Ағаштар
Жиын
Дек
Түбірден кейінгі әр ұрпақта екі ұрпақтан немесе жапырақтардан тұратын иерархиялық құрылым
бинарлық граф
бинарлық ағаш
екілік жүйе
көптармақты ағаштар
Максималды элемент ... түбірінде орналасады
үйінді
тізім
жиын
кезек
Дейкстр, Краскал, Прима, Хаффман алгоритмі жатады
сараң
жылдам
аңқау
пирамидальді
Алгоритм бір түйіннен басқа түйіндерге дейінгі ең кіші жолды табады (графта қабырғалардың салмағы теріс болмауы керек)
Дейкстр
Краскал
Прима
Кнут-Моррис-Пратт
