МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
Ємна та часова складність. Поліноміальна зв’язність.Основними мірами обчислювальною складності алгоритмів є: * часова складність, яка характеризує час, необхідний для виконання алгоритму на даній машині; цей час, як правило, визначається кількістю операцій, які потрібно виконати для реалізації алгоритму; * ємнісна складність, яка характеризує пам'ять, необхідну для виконання алгоритму. Часова та ємнісна складність тісно пов'язані між собою. Обидві є функціями від розміру вхідних даних. Надалі обмежимося тільки аналізом часової складності. Складність алгоритму описується функцією f(n), де n - розмір вхідних даних. Важливе теоретичне і практичне значення має класифікація алгоритмів, яка бере до увагу швидкість зростання цієї функції. Означення. Кажуть, що f(n) = O (g(n)), якщо існує така константа с > 0, що для будь-якого n виконується нерівність: |f(n)| Ј с |g(n)|.Оскільки і розмір вхідних даних, і кількість операцій є величинами невід'ємними (а фактично - додатніми), модулі можна опустити. Виділяють такі основні класи алгоритмів: * логарифмічні: f(n) = O (log2n); * лінійні: f(n) = O (n); * поліноміальні: f(n) = O (nm); тут m - натуральне число, більше від одиниці; при m = 1 алгоритм є лінійним; * експоненційні: f(n) = O (an); a - натуральне число, більше від одиниці. Для однієї й тієї ж задачі можуть існувати алгоритми різної складності. Часто буває і так, що більш повільний алгоритм працює завжди, а більш швидкий - лише за певних умов. Приклад. Часто зустрічається задача пошуку в масиві, яка неформально формулюється таким чином: в заданій послідовності чисел знайти елемент з певним значенням. В загальному випадку застосовується алгоритм послідовного пошуку, який полягає в послідовному перегляді всіх елементів і порівнянні їх з потрібним значенням. Легко бачити, що цей алгоритм має лінійну часову складність. Але, якщо заздалегідь відомо, що послідовність упорядкована за зростанням або за спаданням, можна застосувати інший алгоритм - алгоритм половинного ділення. Послідовність ділиться на дві рівні частини. Оскільки послідовність упорядкована, можна визначити, в якій частині знаходиться потрібний елемент. Після цього процедура повторюється: потрібна частина знову ділиться навпіл і т.п. Цей алгоритм є логарифмічним. Будемо називати часовою складністю задачі часову складність найбільш ефективного алгоритму для її вирішення. На початок Експоненційні алгоритми та перебір Експоненційні алгоритми часто пов'язані з перебором різних варіантів розв'язку.
|
||||||||
|