Записи с меткой «алгоритмы»

Примеры анализа сложности алгоритмов

algorithm_example_4_5

Еще одна статья по анализу алгоритмов? Давным давно я написал статью, в которой была параллельная реализация алгоритма быстрой сортировки [1]. По ней я получил обратную связь. Одни ребята написали мне, что быстрая сортировка будет работать медленнее, чем их реализация (мне скинули «слегка оптимизированный» алгоритм сортировки пузырьком). В качестве аргумента я получил такую фразу: «он (алгоритм …

Рекурсия в программировании. Анализ алгоритмов

merge-sort_flowchart

Рекурсия — это свойство объекта подражать самому себе. Объект является рекурсивным если его части выглядят также как весь объект. Рекурсия очень широко применяется в математике и программировании: структуры данных: граф (в частности деревья и списки) можно рассматривать как совокупность отдельного узла и подграфа (меньшего графа); строка состоит из первого символа и подстроки (меньшей строки); шаблоны …

Анализ сложности алгоритмов. Примеры

asymptotic notation_Omega

Алгоритм — это точное предписание, однозначно определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату [1]. При разработке алгоритмов очень важно иметь возможность оценить ресурсы, необходимые для проведения вычислений, результатом оценки является функция сложности (трудоемкости). Оцениваемым ресурсом чаще всего является процессорное время (вычислительная сложность) и память (сложность алгоритма по памяти). Оценка позволяет предсказать …

Блок-схемы алгоритмов. ГОСТ. Примеры

insertsort_flowchart

Схема — это абстракция какого-либо процесса или системы, наглядно отображающая наиболее значимые части. Схемы широко применяются с древних времен до настоящего времени — чертежи древних пирамид, карты земель, принципиальные электрические схемы. Очевидно, древние мореплаватели хотели обмениваться картами и поэтому выработали единую систему обозначений и правил их выполнения. Аналогичные соглашения выработаны для изображения схем-алгоритмов и закреплены …

Структуры данных. Деревья

Аннотация Статья знакомит читателя с понятием дерева как структуры данных, поясняет в каких случаях и для чего следует применять деревья. В статью также планировалось поместить примеры правил обработки деревьев на языке программирования «Пролог», однако, решено описать их в следующей статье. Тем не менее, это оказало влияние на текст статьи – она не является очень подробной …

Алгоритм. Свойства алгоритма

check-brackets-flowchart

Существует множество определений понятия «алгоритм»: «процедура, которая принимает любой из возможных входных экземпляров задачи и преобразует его в соответствии с требованиями, указанными в условии задачи» [1]; «точное предписание, однозначно определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату» [2]; «конечный набор правил, однозначно раскрывающих содержание и последовательность выполнения операций для систематического решения определенного …