Свойство N log N

Пусть количество элементов N в последовательности равно числу 2, возведенному в степень Р. Тогда Построение графиков логарифмов по основанию 2 является непростой задачей, однако желательно иметь некоторое представление о величине просто равной степени Р в равенстве

В табл. 8.1 иллюстрируется взаимосвязь величин N и Р в пределах их изменения, имеющих практический интерес.

Полезно запомнить некоторые компоненты этой таблицы, особенно выделенные жирным шрифтом; тогда соседние компоненты будут восприниматься как таблица умножения. Если вы не знаете, что 210 приблизительно равно 1000, то вы окажетесь в затруднительном положении при беседах на технические темы. Другим полезным соотношением является следующее: мегабайт.

Таблица 8.1 Значения величин

(см. скан)

Рис. 8.2. Графики зависимостей величин от построенные в логарифмическом масштабе и иллюстрирующие, каким образом быстрые алгоритмы обеспечивают возможность и целесообразность использования значений для широкого круга приложений.

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

Общепринятым является утверждение, что число операций, выполняемых в вышеприведенных равенствах, увеличивается по закону . Это не так очевидно для N = 2, 4 и 8. При больших N возникают сложности в расчете количества этих операций, обусловленные тем, что существенное число коэффициентов принимает значения, равные единице, и в силу этого не требуется умножение; некоторые коэффициенты равны нулю, что исключает выполнение операций и умножения, и деления. Несмотря на подобное усложнение, коэффициенты имеют вполне определенные значения и могут быть рассчитаны для последовательно возрастающих N. Тогда к оценке времени счета можно подойти с позиций определения количества операций сложения и умножения, что воспринимается как увеличение времени счета пропорционально Естественно, имеется также возможность хронометрирования процесса фактических вычислений; этот подход выходит за рамки метода, предусматривающего подсчет количества операций, и предполагает оценку временных затрат на реализацию

соответствующих прецедур, что не учитывается в вышеописанном методе подсчета.

Когда величина N становится большой, зависимость вида означает; что мы столкнемся с практическими пределами для временных затрат или стоимости. Быстрый алгоритм - это алгоритм, не реализующий в чистом виде все операции, предусмотренные в соответствии с определением преобразования, вследствие чего требуемое количество операций пропорционально или , а не . В качестве примера, иллюстрирующего практическое значение этих рассуждений, рассмотрим быстрый алгоритм, для реализации которого требуется по сравнению с для обычного алгоритма дискретного преобразования. На рис. 8.2 построены соответствующие графики зависимости временных затрат от величины Р, изменяющейся от 0 до . Хотя не является наибольшим значением Р, которое может встретиться на практике, оно фигурировало бы при анализе изображений, имеющих структуру вида элементов разрешения, для которых разрешающая способность выше реализуемой при использовании телевизионного экрана. Подавляющее большинство преобразований, осуществляемых в повседневной практике, без сомнения оперирует величинами Р, не превышающими Графики наглядно иллюстрируют, что при цифровой обработке изображений больших размеров крайне важным становится вопрос о скорости реализации алгоритма. Ясно, что введение быстрого преобразования Фурье (БПФ) сильно расширяет наши возможности. Необходимость обработки изображений в реальном времени требует на сегодняшний день еще более высокого быстродействия, и обратно, по мере увеличения быстродействия будут открываться новые приложения.