к экзамену по алгоритмизации и введению в программирование. Экзамен по алгоритмизации учить. Основные этапы решения задач на ЭВМ формулировка задачи(математическая)
 Скачать 258.39 Kb.
|
|
Определение вычислительной сложности алгоритма Вычислительная сложность алгоритма — это функция, определяющая зависимость объёма работы, выполняемой алгоритмом, от свойств входных данных Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. Алгоритм имеет сложность O(f(n)), если при увеличении размера входных данных n, время выполнения алгоритма возрастает с той же скоростью, что и функция f(n). Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Примеры некоторых видов сложности по времени: O(n) — линейная сложность Пример: алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный. O(log n) — логарифмическая сложность Пример: вводится число a, являющееся степенью двойки (2x= a). Нужно найти эту степень, путём деления этого числа на два и подсчёта количества этих делений. O(nс) — полиноминальная (квадратичная...) сложность Пример: алгоритм сортировки пузырьком. Здесь мы не учитываем остальные операции, а только два вложенных цикла, так как только они будут иметь смысл при увеличении кол-ва данных O(сn) — экспоненциальная сложность Пример: вывести на экран все двоичные числа длин N O(1) - не зависящая от размера данных сложность Пример: для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. О(n!) — факториальная Блок схемы алгоритмов линейной структуры - алгоритмы, символы которых изображаются в той последовательности, в которой должны быть выполнены предписываемые ими действия    Блок схемы алгоритмов разветвлённой структуры - алгоритмы, в которых выполнение той или иной последовательности действий происходит в зависимости от результатов проверки какого-либо условия. Блок схемы алгоритмов с итерационным циклом В алгоритмах этого цикла количество требуемых итераций заранее не известно. Выход из итерационного цикла осуществляется в случае невыполнения данного условия. Блок схемы алгоритмов циклической структуры -алгоритмы, в которых предусмотрены неоднократные выполнения операций или последовательности. Основные действия цикла: Начальная инициализация параметров цикла; Изменение значений параметров в конце тела цикла; Проверка условий выполнения (окончания) цикла. Параметр цикла -это переменная которая изменяется при повторении цикла Существует три формы циклов:
|
