Алгоритмы и структуры данных

Наилучшим случаем для алгоритма является такой набор данных, на котором алгоритм выполняется за минимальное время. Такой набор данных представляет собой комбинацию значений, на которой алгоритм выполняет меньше всего действий. Время выполнения алгоритма в наилучшем случае очень часто оказывается маленьким или просто постоянным, поэтому подобный анализ проводится редко.

Операции сравнения Все операторы сравнения считаются эквивалентными, и их учитывают в алгоритмах поиска и сортировки. Важным элементом таких алгоритмов является сравнение двух величин для определения (при поиске) того, совпадает ли данная величина с искомой, а при сортировке - вышла ли она за пределы данного интервала. Операторы сравнения проверяют, равна или не равна одна величина другой, меньше они ли больше, меньше или равна, больше или равна. Арифметические операции Аддитивные операции (сложения) Включают в себя сложение, вычитание, увеличение и уменьшение счетчика. Мультипликативные операции (умножения) Включают в себя умножение, деление и взятие остатка по модулю. Умножения работают дольше, чем сложения. На практике некоторые алгоритмы считаются предпочтительнее других, если в них меньше умножений, даже если число сложений при этом пропорционально возрастает. Целочисленное умножение или деление на степень двойки образуют специальный случай. Эта операция ...

Последовательность действий алгоритма определяется не в последнюю очередь входными данными. Некоторые алгоритмы сортировки могут работать очень быстро, если входной список уже отсортирован, тогда как другие алгоритмы покажут весьма скромный результат на таком списке. А вот на случайном списке результат может оказаться противоположным. Нельзя ограничиваться анализом поведения алгоритмов на одном входном наборе данных. Нужно искать такие данные, которые обеспечивают как самое быстрое , так и самое медленное выполнение алгоритма. Кроме того, нужно оценивать и среднюю эффективность алгоритма на всех возможных наборах данных. При анализе необходимо рассматривать все типы возможных множеств входных значений, поскольку если ограничиться одним множеством, оно может оказаться тем самым, на котором решение самое быстрое (или самое медленное). В результате мы получим ложное представление об алгоритме. Разбиение различных входных множеств на классы в зависимости от поведения алгоритма ...

Программирование - это конструирование. Как вообще можно изучать изобретательное конструирование? Можно попытаться из анализа многих относительно сложных и длинных образцовых примеров программ выделить элементарные композиционные принципы и представить их систематическим образом.  Длинные программы доминируют в практике программирования, и они гораздо больше подходят для демонстрации тех трудно определяемых, но существенных свойств, которые называют стилем и хорошей структурой. Они также должны послужить упражнениями в искусстве чтения программ, которым часто пренебрегают в пользу написания программ. Важно уделять достаточно внимания деталям, так как в программировании дьявол прячется в деталях.

Рекурсивные структуры данных являются важным подклассом часто используемых динамических структур. Хотя рекурсивные определения возможны и даже естественны в этих случаях, на практике они обычно не используются. Вместо них используют явные ссылочные или указательные переменные.

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

В большинстве случаев нет нужды точно подсчитывать количество выполненных операций как функцию от размера входных данных N. Разница между алгоритмом, который делает N + 5 операций, и тем, который делает N + 250 операций, становится незаметной, как только N становится очень большим. Решение вопроса о том, что считать, состоит из двух шагов. На первом шаге выбирается значимая операция или группа операций, а на втором - каких из этих операций содержатся в теле алгоритма, а какие составляют накладные расходы или уходят на регистрацию и учет данных. В качестве значимых обычно выступают операции двух типов: сравнение и арифметические операции . Инициализация Вес инициализации по отношению ко времени выполнения алгоритма незначителен. В терминах анализа при увеличении объёма входных данных стоимость инициализации становится пренебрежимо малой. Алгоритм подсчета числа вхождений различных символов в файл Рассмотрим, например, алгоритм подсчета числа вхождений различных символов в ф...