Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Понятие алгоритма. Понятие о сложности алгоритмовАлгоритм — это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых и точно определенных элементарных операций для решения задачи, общее для класса возможных исходных данных. Разные понятия алгоритма: 1. Колмогоров: Алгоритм - это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи. 2. Марков: Алгоритм - это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату. Для анализа и/или сравнения алгоритмов между собой необходимо ввести некий критерий качества. Основным критерием качества является сложность. Сложность - это количественная оценка ресурсов, затрачиваемых алгоритмом. Ресурсы: Человеческие (создание и понимание алгоритма). Оценивает интеллектуальная сложность. Единого критерия оценки не существует. Вычислительные (на выполнение алгоритма): Память. Оценивает пространственная сложность - количество памяти, требующееся для выполнения алгоритма. Процессорное время. Оценивает временная сложность - количество времени, необходимое на выполнение алгоритма. Если пространственная сложность поддается количественной оценке, то со временной сложностью не все так просто - оценка алгоритма зависит от аппаратуры. Можно сравнивать 2 алгоритма на одинаковой аппаратуре, но чтобы избавиться от аппаратной зависимости используется оценка в виду функции T(n) от количества обрабатываемых данных. Эта оценка применяется к отдельным частям алгоритма, затем комбинируется в общую оценку. Способы оценивания сложности алгоритмов.
|