Често съм се чудил за сложността на изчисляването на времето. Винаги имаше достатъчно теория, но никога достатъчно практически примери, свързани с теорията, която слушах в часовете си по Алгоритъм.

Едно от полетата, в които бях заседнал, беше изчисляването на времевата сложност на рекурсивните алгоритми. Разбира се, знаете методите, но трябва да си ударите главата в стената няколко пъти, преди да разберете как да ги използвате.

Времевата сложност на алгоритъм обикновено се изразява с помощта на нотация с голямо O, която изключва коефициенти и членове от по-нисък ред. Обикновено се оценява чрез преброяване на броя на елементарните операции, извършени от алгоритъма, като изпълнението на елементарна операция отнема фиксирано време. По този начин количеството необходимо време и броят на елементарните операции, извършени от алгоритъма, се различават най-много с постоянен фактор.

Времевата сложност на рекурсивните алгоритми е трудно нещо за изчисляване, но ние знаем два метода, единият от които е основната теорема, а другият е методът на Акра-Бази. Последният използва по-математически базиран подход. В тази статия няма да обяснявам какво е нотация голямо О (предполагам, че читателят вече го знае), а само ще обясня как да използвам и двата метода за изчисляване на времевата сложност на рекурсивните алгоритми.

ГЛАВНАТА ТЕОРЕМА

Основната теорема се отнася до рекурентни отношения от формата:

където

Където

  • е размерът на проблема,

  • е броят на подпроблемите в рекурсията,

  • е размерът на всеки подпроблем,

  • е цената на работата, извършена извън рекурсивните извиквания (включва разходите за разделяне на проблема и разходите за обединяване на решенията на подпроблемите)

Това е математическото определение, нека го поставим в по-формално определение за изчисляване на времевата сложност. Позволявам

където

са константи. Ако е приложимо следното

за някои

тогава:

Винаги съм обичал тези формални определения, но нека дадем пример:

Връзката на повторение отговаря на нашето определение по-горе. Константите са

и

Сега трябва да се запитаме следното:

Кой оператор се вписва в средата. Нашата функция е

следователно можем да кажем, че нашата функция е

Проверяваме експонентата

така че нашите

Сега нека вмъкнем стойностите в горното уравнение:

Следователно нашият оператор тук е равен и попадаме в условие две от уравнението по-горе. Следователно нашата времева сложност е:

Това са примери, които можете да намерите навсякъде. Но проблемът е какво правите, когато получите алгоритъм пред вас? Нека проверим следния алгоритъм:

Трябва да напишем този алгоритъм в рекурентна релация във формата, която сме написали по-горе. Как да направим това? Сега нека изброим нещата, които трябва да намерим в кода по-горе:

  • намерете рекурсията и броя пъти, в които рекурсията се изпълнява във всеки цикъл (брой подпроблеми в рекурсията),
  • трябва да намерим цената на работата, извършена извън рекурсията,
  • трябва да намерим размера на всеки подпроблем

От кода по-горе можем ясно да видим къде се извършва рекурсията, като извикаме методаалгоритъм в цикъла for. Можем да видим, че това извикване се изпълнява три пъти (цикълът for преминава от 0, докато стане по-малък от 4) и че размерът на всеки подпроблем е

(аргументът, когато извикваме метода рекурсивно). Така че можем да кажем това

Преди извикването на рекурсия се изпълнява друг for цикъл и това е работата, която се извършва извън извикването на рекурсия. Този цикъл се изпълнява n пъти, така че нашата работа извън рекурсията е n. Следователно нашата функция е равна на n. Така че, ако съберем всичко заедно:

Сега нека съберем всичко заедно:

Нека се запитаме същото като с горната връзка:

Нашият оператор отново е равен и попадаме във второто условие. Следователно времевата сложност е:

Основният метод е прост, но има своите недостатъци. Ако имаме различни рекурсии в един алгоритъм, трябва да прибегнем до други методи за решаване на нашите времеви сложности.

МЕТОДЪТ НА AKRA BAZZI

Akra Bazzi се използва, когато подпроблемите на нашия алгоритъм имат значително различни размери. Позволявам:

Условията за ползване са:

са положителни константи,

са константи между 0 и 1,

за някои

за всеки

за всеки

Ако всички тези условия са изпълнени, тогава можем да кажем, че:

където

решава уравнението

Отново, макар да обичам определенията, примерите са тези, които ни учат най-много. Нека вземем два различни примера, един, където е зададена връзката на повторение, и един, където получаваме алгоритъм.

Тук

нашата функция

Константите са достатъчни за нашите условия. Функцията е асимптотично ограничена отгоре с полином (например

Функциите

са постоянни и следователно са асимптотично ограничени от

Последното ни условие гласи, че нашата рекурентна връзка трябва да бъде дефинирана и окончателна за първите шест случая.

Нека намерим стойностите за

което решава уравнението

Решението е

Сега можем да изчислим интеграла.

Обърнете внимание, че съм пропуснал някои стъпки при изчисляването на стойността на интеграла, той може да бъде решен чрез използване на метода на заместване

Сега нека вземем един практически пример. Разгледайте следния алгоритъм:

Процедурата, която ще предприемем, е точно същата като тази с основната теорема. Имаме три рекурсивни извиквания във функцията, но две от тях имат еднакъв размер на подпроблема, така че просто ще умножим двете. Работата, извършена извън рекурсията, е равна

(условието, при което i е по-малко от n квадрат, така че цикълът се изпълнява n квадратни пъти). Следователно нашата рекурентна връзка е:

Нека зададем уравнението:

Взехме само числата, които имаха T в горното уравнение и ги умножихме по пъти, когато рекурсията се повтаря. Решението на уравнението е

Сега, за да го решим, трябва да го вмъкнем във формулата по-горе:

Имайте предвид, че това беше лесно. Уравненията могат да станат много по-трудни и знанията за интегриращи функции са основата тук, така че не забравяйте да обърнете внимание в часа си по компютърни науки.

РЕФЕРЕНЦИИ

  1. Томас Х. Кормен, Чарлз Е. Лейзерсън, Роналд Л. Ривест и Клифърд Стайн. Въведение в алгоритмите, второ издание. MIT Press и McGraw-Hill, 2001 г. ISBN 0–262–03293–7. Раздели 4.3 (Главният метод) и 4.4 (Доказателство на главната теорема), стр. 73–90.
  2. Мохамад Акра, Луай Бази: За решаването на линейни рекурентни уравнения. Изчислителна оптимизация и приложения 10(2):195–210, 1998.