Главная » Ядро Linux » Сложность алгоритмов

0

компьютерных и связанных с ними  дисциплинах полезно выражать  сложность, или масштабируемость, алгоритмов с помощью количественных значащих характеристик (в  отличие   от менее  наглядных характеристик,  таких  как  быстрый или  медленный).  Существуют различные методы  представления масштабируемости. Один  из наиболее часто  используемых подходов — это исследование асимптотического поведения алгоритмов. Асимптотическое поведение — это поведение алгоритма при достаточно больших  значениях входных  параметров или, другими  словами, при стремлении входных параметров к бесконечности. Асимптотическое поведение показывает, как  масштабируется алгоритм, когда  его входные  параметры принимают все большие и большие значения. Исследование масштабируемости алгоритмов, т.е. изучение  свойств  алгоритма при  больших  значениях входных  параметров, позволяет смоделировать поведение алгоритма по отношению к тестовым  задачам  и лучше по-

нять особенности этого поведения.

Алгоритмы

Алгоритм  — это  последовательность действий, возможно, с одним  входом  или более  и, в конечном счете, с одним  результатом или  выходом.  Например, подсчет количества людей  в комнате представляет собой  алгоритм, для которого люди, находящиеся в комнате, являются входными данными, а количество людей в комнате — выходными данными. Операции замещения страниц в ядре Linux или планирование выполнения процессов — это тоже примеры алгоритмов. Математически алгоритм аналогичен функции (или, по крайней мере, может  быть смоделирован с помощью функции). Например, если мы обозначим алгоритм подсчета  людей в комнате буквой  f, а количество людей, которых  необходимо посчитать, буквой  х, то функцию подсчета  количества людей  можно  записать следующим образом.

y=f(х)

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

Источник: Лав,  Роберт. Разработка ядра  Linux, 2-е  издание. : Пер.  с англ.  — М.  : ООО  «И.Д.  Вильяме» 2006. — 448 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии