Роберт Лав - Разработка ядра Linux

Если f ( x ) принадлежит множеству большого O ( g ( x )) , то ∃ c и x ', такие что f ( x )≤c∙ g ( x ), ∀ x > x '

Это означает, что время вычисления функции f ( x ) всегда меньше времени вычисления функции g ( x ), умноженного на некоторую константу, и это справедливо всегда, для всех значений x , больших некоторого начального значения х '.

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

Когда говорят об обозначении большого-О, то чаще всего имеют в виду то, что Дональд Кнут (Donald Knuth) описывал с помощью обозначения "большого-тета". Обозначение "большого-О" соответствует верхней границе. Например, число 7 — это верхняя граница числа 6, кроме того, числа 9, 12 и 65 — это тоже верхние границы числа 6. Когда рассматривают рост функции, то обычно наиболее интересна наименьшая верхняя граница или функция, которая моделирует как верхнюю, так и нижнюю границу [100] Если интересно, то нижняя граница описывается с помощью обозначения большого-омега. Определение аналогично определению множества большого-О, за исключением того, что значения функции g ( x ) должны быть меньше значений функции f ( x ) или равны им. . Профессор Кнут описывает это с помощью обозначения большого-тета следующим образом.

Если f ( x ) принадлежит множеству большого-тета от g ( x ), то g ( x ) является одновременно и верхней и нижней границей f ( x )

Можно также сказать, что функция f ( x ) порядка функции g ( x ). Порядок, или множество "большого-тета" алгоритма, — один из наиболее важных математических инструментов изучения алгоритмов.

Следовательно, когда говорят об обозначении большого-О, то чаще всего имеют в виду наименьший возможный вариант "большого-О" — "большое-тета". Об этом не нужно особо волноваться, если, конечно, нет желания доставить удовольствие профессору Кнуту.

Вернемся снова к подсчету количества людей в комнате. Допустим, что можно считать по одному человеку за секунду. Следовательно, если в комнате находится 7 человек, то подсчет займет 7 секунд. Очевидно, что если будет n человек, то подсчет всех займет n секунд. Поэтому можно сказать, что этот алгоритм масштабируется, как O ( n ). Что если задача будет состоять в том, чтобы станцевать перед всеми, кто находится в комнате? Поскольку, независимо от того, сколько человек будет в комнате, это займет одно и то же время, значит, этот алгоритм масштабируется, как O (1). В табл. В.1 показаны другие часто встречающиеся характеристики сложности.

Таблица В.1. Значения масштабируемости алгоритмов во времени

Как масштабируется алгоритм представления всех людей в комнате друг другу? Какая функция может промоделировать этот алгоритм? Для представления одного человека необходимо 30 секунд, сколько времени займет представление 10 человек друг другу? Что будет в случае 100 человек?

Очевидно, что будет разумным избегать алгоритмов, которые масштабируются, как О ( n !) или O (2ⁿ). Более того, замена алгоритма, который масштабируется, как O ( n ), алгоритмом, который масштабируется, как O (1), — это обычно серьезное улучшение. Тем не менее это не всегда так, и нельзя принимать решение вслепую, базируясь только на описании "большого-О". Вспомните, что в определении множества О ( g ( x )) фигурирует константа, на которую умножается значение функции g ( x ). Поэтому есть возможность, что алгоритм, который масштабируется, как O ( 1 ), будет выполняться в течение 3 часов. Следовательно, он будет выполняться всегда в течение 3 часов, независимо от количества входных данных, но это может оказаться дольше, по сравнению с алгоритмом, который масштабируется, как O ( n ), при небольшом количестве входных данных. При сравнении алгоритмов необходимо всегда принимать во внимание количество входных данных. Не стоит слепо оптимизировать для некоторого случайно выбранного варианта.

Список литературы отсортирован и содержит некоторые из самых интересных и полезных книг, которые близки по теме, или дополняют материал данной книги.

Полезность этих книг проверена временем. Некоторые из них представляют собой "священные писания" но соответствующим темам, в то время как другие просто кажутся автору интересными, глубокими или занимательными. Автор надеется, что читателю они тоже окажутся полезными.

Наилучшая ссылка на "дополнительное чтение", которая лучше всего дополняет материал данной книги — это исходный код ядра. Для работы с ОС Linux у нас есть неограниченный доступ к полному исходному коду ядра современной операционной системы. Не принимайте это как должное! Разберитесь с ним! Читайте код! Пишите код!

В этих книгах рассмотрены принципы работы операционных систем в объеме учебных курсов. В них описываются основные понятия, алгоритмы и проблемы, связанные с построением высокофункциональных операционных систем, а также решения указанных проблем. Все эти книги могут быть рекомендованы, но если нужно выделить одну, то это, конечно, книга H. Deitel.

• Deitel H., Deitel P. and Choffnes D. Operating Systems . Prentice Hall, 2003. Прекрасная книга по теории операционных систем с отличными примерами из теории и практики. Автор помогал в техническом редактировании этой книги, что, может быть, и является причиной его предвзятого отношения, но все же хочется верить, что от этого книга стала значительно лучше.

• Tanenbaum Andrew. Operating Systems: Design and Implementation .. Prentice Hall, 1997. Хорошие начальные сведения об основах построения, принципах работы и реализации Unix-подобной операционной системы Minix.

• Tanenbaum Andrew. Modern Operating Systems . Prentice Hall, 2001. Детальный обзор стандартных проблем разработки операционных систем, а также обсуждение многих концепций, которые используются в современных операционных системах, таких как Unix и Windows.