Теория на изчислителната сложност - отдел на теорията на изчисленията, чиято основна цел е да се определи количеството ресурси, необходими за решаване на изчислителни задачи. Разгледаните ресурси са такива стойности като време, памет или брой процесори.
Юрис Хартманис и Ричард Стърнс се считат за създатели на тази теория. Като примери за t.z.o. можете да зададете проблема за съответствие, проблемът с най-краткия път, проблемът с факторизацията и многодруги, за които се знае, че са изчислими. Теорията за изчислимостта, която е вторият важен клон на теорията за изчисляване, се занимава с въпроса за изчислимостта.
Резултатите, предоставени от t.z.o., могат да бъдат разделени на две категории: положителни и отрицателни, т.е. Положителните резултати се получават по-лесно и обикновено имат формата на алгоритъм, който решава даден проблем заедно с доказателство за коректност и описание на необходимите ресурси.
Сложност на алгоритмите
Количеството ресурси, необходими за изпълнение на алгоритъма, може да се разбира като неговата сложност. В зависимост от разглеждания ресурс, говорим за сложност на времето или сложност на паметта.
Copyright 2024 puzzlefactory.com Всички права запазени.
