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

Анализ среднего случая является самым сложным, поскольку он требует учета множества разнообразных деталей.  В основе анализа лежит определение различных групп, на которые следует разбить возможные входные наборы данных. На втором шаге определяется вероятность, с которой входной набор данных принадлежит каждой группе. На третьем шаге подсчитывается время работы алгоритма на данных из каждой группы. Время работы алгоритма на всех входных данных одной группы должно быть одинаковым, в противном случае группу следует разбить ещё раз. Среднее время работы вычисляется по формуле: ,  где n - размер входных данных; m - число групп; p i - вероятность того, что входные данные принадлежат группе с номером i; t i - время необходимое алгоритму для обработки данных из группы с номером i. И разбиение на группы, и значения параметров p i  и t i  зависят от n. Если вероятность попадания входных данных в каждую из групп одинакова, то среднее время работы ...

Анализ наихудшего случая говорит о максимальном времени работы алгоритма. Анализ наихудшего случая даёт верхние оценки для времени работы частей программы в зависимости от выбранных алгоритмов. При анализе наихудшего случая необходимо найти входные данные, на которых алгоритм будет выполнять больше всего работы.

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

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

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