Оценка размера входных данных

Время выполнения большинства алгоритмов напрямую зависит от размера вводимых данных (т.е. чем больше размер, тем дольше работает алгоритм). Например, довольно долго длится процесс сортировки больших массивов данных, перемножения больших матриц и т.п. Поэтому вполне логично описать эффективность алгоритма в виде функции от некоторого параметра n, связанного с размером входных данных. В большинстве случаев выбрать такой параметр не представляет большого труда. Например, для задач, связанных с сортировкой, поиском, нахождением наименьшего элемента в списке и многих других, связанных с обработкой списков, таким параметром будет размер списка. Для задачи вычисления значения многочлена степени n таким параметром может быть степень многочлена или количество его коэффициентов, которое на единицу больше степени многочлена. Конечно, бывают случаи, когда выбор параметра, показывающего размер входных данных, имеет особое значение. Один из примеров подобных случаев — перемножение двух матриц размером nхn. Существует две подходящих единицы измерения размера данной задачи. Первая и наиболее часто используемая — это порядок матрицы n. Однако существует и другая, не менее подходящая единица измерения, — количество перемножаемых элементов в матрицах. Последняя единица к тому же более универсальна, поскольку ее можно применять не только к квадратным матрицам. Поскольку существует простая формула, связывающая эти две единицы измерения, мы легко можем перейти от одной единицы к другой, однако искомая эффективность алгоритма будет в значительной степени отличаться в зависимости от того, какая из двух единиц измерения была использована при решении задачи. На выбор подходящей системы измерений размера задачи могут повлиять выполняемые рассматриваемым алгоритмом действия. Например, как оценить размер входных данных для алгоритма, выполняющего проверку орфографии? Если в алгоритме проверяется каждый вводимый символ, то оценить размер входных данных мы можем, подсчитав количество символов во входном потоке. Если же в алгоритме происходит обработка текста по словам, то нужно подсчитать количество слов во входном потоке. Мы должны сделать специальное замечание по поводу оценки размера входных данных для алгоритмов, связанных с нахождением чисел, удовлетворяющих определенным условиям (например, проверяющих, является ли заданное целое число n простым). Для подобных алгоритмов кибернетики предпочитают оценивать размер входных данных по количеству битов b в двоичном представлении числа n: Подобная система измерений позволяет лучше оценить эффективность рассматриваемого алгоритма.

Дата добавления: 2014-01-20