По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
Из предыдущих статей (тут и тут) мы узнали, что очень немногие механизмы, учитывают изменения в топологии. Большинство этих решений ориентированы на вычисления loop-free пути через очевидно стабильную сеть. Но что происходит при изменении топологии? Как сетевые устройства создают таблицы, необходимые для пересылки пакетов по loop-free путям в сети?
В этой серии статей мы рассмотрим очередную подзадачу этой всеобъемлющей проблемы и ответим на вопрос: Как плоскости управления обнаруживают изменения в сети и реагируют на них?
На этот вопрос мы ответим, рассмотрев две составляющие процесса конвергенции в плоскости управления. Процесс конвергенции в сети может быть описан в четыре этапа. Рисунок 1 используется для справки при описании этих четырех стадий. Как только связь [C,E] выходит из строя, должны произойти четыре этапа: обнаружение, распространение, вычисление и установка.
Обнаружение изменения: будь то включение нового устройства или линии связи, или удаление устройства или линии связи, независимо от причины, изменение должно быть обнаружено любыми подключенными устройствами. На рисунке 1 устройства C и E должны обнаруживать отказ канала [C, E]; когда линия восстанавливается, они также должны обнаружить включение этой (очевидно новой) линии связи в топологию.
Распространение информации об изменении: каждое устройство, участвующее в плоскости управления, должно каким-то образом узнавать об изменении топологии. На рисунке 1 устройства A, B и D должны каким-то образом уведомляться о сбое канала [C, E]; когда линия будет восстановлена, они должны быть снова уведомлены о включении этой (очевидно новой) линии связи в топологию.
Вычисление нового пути к пункту назначения без петель: на рисунке 1 B и C должны вычислить некоторый альтернативный путь, чтобы достичь пунктов назначения за пределы E (или, возможно, непосредственно самого E).
Установка новой информации о пересылке в соответствующие локальные таблицы: На рисунке 1 B и C должны установить вновь вычисленные loop-free пути к пунктам назначения за пределами E в свои локальные таблицы пересылки, чтобы трафик мог коммутироваться по новому пути.
Далее мы сосредоточимся на первых двух из четырех шагов, описанных в предыдущем списке, размышляя в начале об обнаружении изменений топологии. Будут рассмотрены некоторые примеры протоколов, специализирующихся на обнаружении изменений топологии. Распределение топологии и информации о достижимости будет рассмотрена в конце этой серии статей. Поскольку эта проблема, по сути, является проблемой распределенной базы данных, она будет решаться с этой точки зрения.
Обнаружение изменений топологии
Первым шагом в реакции на изменение топологии сети является обнаружение изменения. Вернемся к рисунку 1. Каким образом два устройства, подключенные к каналу, C и E, обнаруживают сбой канала? Решение этой проблемы не так просто, как может показаться на первый взгляд, по двум причинам: информационная перегрузка и ложные срабатывания.
Информационная перегрузка возникает, когда плоскость управления получает так много информации, что просто не может распространять информацию об изменениях топологии и/или вычислять и устанавливать альтернативные пути в соответствующие таблицы на каждом устройстве достаточно быстро, чтобы поддерживать согласованное состояние сети. В случае быстрых, постоянно происходящих изменений, таких как отключение связи и подключение каждые несколько миллисекунд, плоскость управления может быть перегружена информацией, в результате чего сама плоскость управления потребляет достаточно сетевых ресурсов, чтобы вызвать сбой сети. Также возможно, что серия отказов вызовет петлю положительной обратной связи, и в этом случае плоскость управления “сворачивается” сама по себе, либо реагируя очень медленно, либо вообще отказывая. Решение проблемы информационной перегрузки состоит в том, чтобы скрыть истинное состояние топологии от плоскости управления до тех пор, пока скорость изменения не окажется в пределах, которые может поддерживать плоскость управления.
Ложные срабатывания - это проблема второго типа. Если канал отбрасывает один пакет из каждых 100, и каждый раз отбрасывается единственный пакет, который оказывается пакетом плоскости управления, используемым для отслеживания состояния канала, будет казаться, что канал выходит из строя и довольно часто возобновляет работу - даже если другой трафик перенаправляется по каналу без проблем.
Существует два широких класса решений проблемы обнаружения событий:
Реализации могут периодически отправлять пакеты для определения состояния канала, устройства или системы. Это опрос (Polling).
Реализации могут вызвать реакцию на изменение состояния канала или устройства в некотором физическом или логическом состоянии внутри системы. Это обусловлено событиями.
Как всегда, есть разные компромиссы с этими двумя решениями и подкатегории каждого из них.
Опрос (Polling) для обнаружения сбоев.
Опрос может выполняться удаленно или вне диапазона, или локально, или в группе. Рисунок 2 демонстрирует это.
На рисунке 2 A и B периодически отправляют приветствие или какой-либо другой пакет опроса по тому же каналу, через который они подключены, и по тому же каналу, по которому они пересылают трафик. Это внутриполосный опрос, который имеет преимущество отслеживания состояния канала, по которому пересылается трафик, передается информация о доступности и т. д. С другой стороны, D запрашивает у A и B некоторую информацию о состоянии канала [A, B] из другого места в сети. Например, D может периодически проверять состояние двух интерфейсов на канале [A, B] или, возможно, периодически отправлять пакет по пути [C, A, B, C] и т. д. Преимущество заключается в том, что информация о состоянии большого количества каналов может быть централизована, что упрощает управление сетью и устранение неполадок. Оба типа опроса часто используются в реальных сетевых развертываниях.
Для работы механизмов опроса часто используются два отдельных таймера:
Таймер для определения частоты передачи опроса. Он часто называется интервалом опроса в случае внеполосного опроса и часто называется таймером приветствия в случае внутриполосного опроса.
Таймер, чтобы определить, как долго ждать, прежде чем объявить связь или устройство отключенным, или включить сигнал тревоги. Это часто называют мертвым интервалом или мертвым таймером в случае внутриполосного опроса.
Цели внутриполосного и внеполосного опроса часто различаются. Внеполосный опрос для обнаружения изменений в состоянии сети часто (но не всегда - особенно в случае централизованной плоскости управления) используется для мониторинга состояния сети и позволяет централизованно реагировать на изменения в состоянии. Внутриполосный опрос наиболее часто используется (как и следовало ожидать) для локального обнаружения изменений состояния, чтобы управлять реакцией распределенных плоскостей управления.
Обнаружение сбоев на основе событий
Обнаружение сбоев на основе событий основывается на некотором локальном, измеримом событии для определения состояния конкретного канала или устройства. Рисунок 3 демонстрирует это.
На рисунке 3, который показывает одну из возможных реализаций элементов архитектуры между физическим интерфейсом и протоколом маршрутизации, есть четыре шага:
Связь между двумя микросхемами физического интерфейса (phy), расположенными на обоих концах связи, не работает. Микросхемы физического интерфейса обычно являются оптическими для электрических передач обслуживания. Большинство микросхем физического интерфейса также выполняют некоторый уровень декодирования входящей информации, преобразуя отдельные биты в сети в пакеты (десериализация) и пакеты в биты (сериализация). Информация кодируется физическим интерфейсом на носителе, который предоставляется двумя физическими микросхемами, подключенными к физическому носителю. Если канал не работает или один из двух интерфейсов отключен по какой-либо причине, микросхема физического интерфейса на другом конце канала увидит падение несущей почти в реальном времени - обычно в зависимости от скорости света и длины физического носителя. Это состояние называется потерей носителя.
Микросхема физического интерфейса при обнаружении потери несущей отправляет уведомление в таблицу маршрутизации (RIB) на локальном устройстве. Это уведомление обычно запускается как прерывание, которое затем транслируется в некоторую форму вызова интерфейса прикладного программирования (API) в код RIB, что приводит к тому, что маршруты, доступные через интерфейс, и любая информация о следующем переходе через интерфейс помечаются как устаревшие или удаляются из таблицы маршрутизации. Этот сигнал может или не может проходить через базу пересылаемой информации (FIB) по пути, в зависимости от реализации.
RIB будет уведомлять протокол маршрутизации о маршрутах, которые он только что удалил из локальной таблицы, на основе события отключения интерфейса.
Протокол маршрутизации затем может удалить любых соседей, доступных через указанные интерфейсы (или, скорее, через подключенные маршруты).
На рисунке 3 нет места, в котором бы присутствовал периодический процесс, проверяющий состояние чего-либо, а также не было бы пакетов, перемещающихся по сети. Весь процесс основан на том, что микросхема физического интерфейса теряет носитель на подключенной среде, следовательно, этот процесс управляется событиями.
Часто бывает, что состояние, управляемое событиями, и статус опроса совмещаются. Например, на рисунке 3, если бы станция управления периодически опрашивала статус интерфейса в локальном RIB, процесс от набора микросхем физического интерфейса к RIB был бы управляемым событием, а процесс от RIB на станцию управления будет направлен опросом.
Сравнение обнаружения на основе событий и на основе опроса
Таблица 1 отображает преимущества и недостатки каждого механизма обнаружения событий.
Внеполосный опросВнутриполосный опросУправляемый событиямиРаспределение статусовСтатус управляется централизованной системой; централизованная система имеет более полное представление об общем состоянии сетиСтатус определяется локальными устройствами; для получения более широкой картины состояния всей сети требуется сбор информации с каждого отдельного сетевого устройстваСтатус определяется локальными устройствами; для получения более широкой картины состояния всей сети требуется сбор информации с каждого отдельного сетевого устройстваСвязь состояния пересылки со связью или состоянием устройстваСообщение о состоянии связи и / или устройства может быть ложным; не проверяет возможность пересылки напрямуюСостояние канала и/или устройства может быть напрямую связано с возможностью пересылки (исключение сбоев в механизме проверки состояния)Состояние канала и/или устройства может быть напрямую связано с возможностью пересылки (исключение сбоев в механизме проверки состояния)Скорость обнаруженияПеред объявлением канала или устройства должен пройти некоторый интервал ожиданияне удалось предотвратить ложные срабатывания; замедляет сообщение об изменениях в сетиПеред объявлением канала или устройства должен пройти некоторый интервал ожиданияне удалось предотвратить ложные срабатывания; замедляет сообщение об изменениях в сетиНекоторый таймер перед сообщением о сбоях может быть желательным, чтобы уменьшить сообщение о ложных срабатываниях, но этот таймер может быть очень коротким и подкрепляться двойной проверкой состояния самой системы; как правило, гораздо быстрее при сообщении об изменениях сетиМасштабированиеДолжен передавать периодические опросы, потребляя пропускную способность, память и циклы обработки; масштабируется в этих пределахДолжен передавать периодические опросы, потребляя пропускную способность, память и циклы обработки; масштабируется в этих пределахНебольшие объемы текущего локального состояния; имеет тенденцию масштабироваться лучше, чем механизмы опроса
Хотя может показаться, что обнаружение, управляемое событиями, всегда должно быть предпочтительным, есть некоторые конкретные ситуации, когда опрос может решить проблемы, которые не могут быть решены механизмами, управляемыми событиями. Например, одно из главных преимуществ систем, основанных на опросе, особенно при внутриполосном развертывании, заключается в том, чтобы «видеть» состояние невидимых блоков. Например, на рисунке 4 два маршрутизатора соединены через третье устройство, обозначенное на рисунке как ретранслятор.
На рисунке 4 устройство B представляет собой простой физический повторитель. Все, что он получает по каналу [A, B], он повторно передает, как и получил, по каналу [B, C]. На этом устройстве нет какой-либо плоскости управления (по крайней мере, о том, что известно A и C). Ни A, ни C не могут обнаружить это устройство, поскольку оно не изменяет сигнал каким-либо образом, который мог бы измерить A или C.
Что произойдет, если канал [A, B] выйдет из строя, если A и B используют управляемый событиями механизм для определения состояния канала? A потеряет несущую, конечно, потому что физический интерфейс в B больше не будет доступен. Однако C будет продолжать принимать несущую и, следовательно, вообще не обнаружит сбой соединения. Если A и C могут каким-то образом общаться с B, эту ситуацию можно разрешить. Например, если B отслеживает все запросы протокола разрешения адресов (ARP), которые он получает, он может, когда канал [A, B] разрывается, каким-то образом отправить «обратный ARP», уведомляющий B о том, что A больше недоступен. Другое решение, доступное в этой ситуации, - это своего рода опрос между A и C, который проверяет доступность по всему каналу, включая состояние B (даже если A и C не знают, что B существует).
С точки зрения сложности, управляемое событиями обнаружение увеличивает поверхности взаимодействия между системами в сети, в то время как опрос имеет тенденцию сохранять состояние внутри системы. На рисунке 3 должен быть какой-то интерфейс между чипсетом физического интерфейса, RIB и реализацией протокола маршрутизации. Каждый из этих интерфейсов представляет собой место, где информация, которая может быть лучше скрыта через абстракцию, передается между системами, и интерфейс, который должен поддерживаться и управляться. Опрос, с другой стороны, часто может проводиться в рамках одной системы, полностью игнорируя существующие механизмы и технологии.
Пример: обнаружение двунаправленной переадресации
В этом подразделе будет изучен пример протокола, разработанного специально для определения состояния канала в сети. Ни один из этих протоколов не является частью более крупной системы (например, протокола маршрутизации), а скорее взаимодействует с другими протоколами через программные интерфейсы и индикаторы состояния.
Обнаружение двунаправленной переадресации (Bidirectional Forwarding Detection - BFD) основано на одном наблюдении: на типичном сетевом устройстве работает множество плоскостей управления, каждая со своим собственным механизмом обнаружения сбоев. Было бы более эффективно использовать один общий механизм обнаружения для всех различных плоскостей управления. В большинстве приложений BFD не заменяет существующие протоколы приветствия, используемые в каждой плоскости управления, а скорее дополняет их. Рисунок 5 демонстрирует это.
В модели BFD, скорее всего, будет по крайней мере два различных процесса опроса, работающих по одному и тому же логическому каналу (их может быть больше, если есть логические каналы, наложенные поверх других логических каналов, поскольку BFD также может использоваться в различных технологиях сетевой виртуализации). Опрос плоскости управления будет использовать приветствия (hellos) для обнаружения соседних устройств, выполняющих один и тот же процесс плоскости управления, для обмена возможностями, определения максимального блока передачи (MTU) и, наконец, для того, чтобы убедиться, что процесс плоскости управления на соседнем устройстве все еще работает. Эти приветствия проходят через соединение плоскости управления на рисунке 5, которое можно рассматривать как своего рода «виртуальный канал», проходящий через физический канал.
Опрос BFD будет выполняться под соединением уровня управления, как показано на рисунке, проверяя работу физического соединения и плоскостей пересылки (переадресации) на двух подключенных устройствах. Этот двухуровневый подход позволяет BFD работать намного быстрее, даже в качестве механизма опроса, чем любой механизм обнаружения на основе протокола маршрутизации.
BFD может работать в четырех различных режимах:
Асинхронный режим: в этом режиме BFD действует как облегченный протокол приветствия. Процесс BFD в A, потенциально работающий в распределенном процессе (или даже в специализированной интегральной схеме [ASIC]), отправляет пакеты приветствия в C. Процесс BFD в C подтверждает эти пакеты приветствия. Это довольно традиционное использование опроса через hellos.
Асинхронный режим с эхом: в этом режиме процесс BFD в A будет отправлять пакеты приветствия в C, поэтому пакеты приветствия будут обрабатываться только через путь пересылки, что позволяет опрашивать только путь пересылки. Для этого A отправляет пакеты приветствия в C, сформированные таким образом, что они будут переадресованы обратно в A. Например, A может отправить пакет C с собственным адресом A в качестве пункта назначения. C может забрать этот пакет и переслать его обратно к A. В этом режиме приветствия, передаваемые A, полностью отличаются от приветствий, передаваемых C. Подтверждения нет, только две системы посылают независимые приветствия, которые проверяют связь в двух направлениях с каждого конца.
Режим запроса: В этом режиме два одноранговых узла BFD соглашаются отправлять приветствия только тогда, когда подключение должно быть проверено, а не периодически. Это полезно в том случае, когда существует какой-то другой способ определения состояния канала—например, если канал [A, C] является каналом Ethernet, что означает, что обнаружение несущей доступен для обнаружения сбоя канала, - но этот альтернативный метод не обязательно является надежным для обеспечения точного состояния соединения во всех ситуациях. Например, в случае «коммутатора посередине», где B отключен от A, но не C, C может послать BFD привет, отметив любую проблему с подключением, чтобы убедиться, что его соединение с A все еще есть. В режиме запроса некоторые события, такие как потерянный пакет, могут вызвать локальный процесс для запуска события обнаружения BFD.
Режим запроса с эхом: этот режим похож на режим запроса - обычные приветствия не передаются между двумя устройствами, на которых работает BFD. Когда пакет передается, он отправляется таким образом, чтобы другое устройство переадресовало пакет приветствия обратно отправителю. Это снижает нагрузку на процессор на обоих устройствах, позволяя использовать гораздо более быстрые таймеры для приветствий BFD.
Независимо от режима работы, BFD вычисляет различные таймеры опроса (hello) и обнаружения (dead) отдельно по каналу связи. Лучший способ объяснить этот процесс-на примере. Предположим, что A отправляет управляющий пакет BFD с предлагаемым интервалом опроса 500 мс, а C отправляет управляющий пакет BFD с предлагаемым интервалом опроса 700 мс. Для связи выбирается большее число или, скорее, более медленный интервал опроса. Объясняется это тем, что более медленная система должна быть в состоянии идти в ногу с интервалом опроса, чтобы предотвратить ложные срабатывания.
Частота опроса изменяется при фактическом использовании, чтобы предотвратить синхронизацию пакетов приветствия в нескольких системах на одном и том же проводе. Если было четыре или пять систем, развертывающих Border Gateway Protocol (BGP) на одном канале множественного доступа, и каждая система устанавливает свой таймер для отправки следующего пакета приветствия на основе получения последнего пакета, все пять систем могут синхронизировать их передачу приветствия, чтобы все приветствия по сети передавались в один и тот же момент. Поскольку BFD обычно работает с таймерами длиной менее одной секунды, это может привести к тому, что устройство будет получать приветствия от нескольких устройств одновременно и не сможет обрабатывать их достаточно быстро, чтобы предотвратить ложное срабатывание.
Конкретная используемая модификация заключается в джиттере пакетов. Каждый передатчик должен взять базовый таймер опроса и вычесть некоторое случайное количество времени, которое составляет от 0% до 25% от таймера опроса. Например, если таймер опроса составляет 700 мсек, как в приведенном примере, A и C будут передавать каждый пакет приветствия примерно между 562 и 750 мсек после передачи последнего приветствия.
Последний момент, который следует учитывать, - это количество времени, в течение которого A и C будут ждать перед объявлением соединения (или соседа) отключенным. В BFD каждое устройство может вычислить свой собственный таймер отключения, обычно выраженный как кратное таймеру опроса. Например, A может решить считать канал (или C) отключенным после пропуска двух приветствий BFD, в то время как C может решить дождаться пропуска трех приветствий BFD.
Когда узел в кластере vSAN, запущенный в vSphere 6.0 Update 1b, отключен для обслуживания, узлы ESXi в кластере сообщают об ошибке: Host cannot communicate with all other nodes in virtual SAN enabled cluster (Узел не может взаимодействовать со всеми другими узлами кластера с поддержкой виртуальной SAN)
После перезагрузки узла (узлов) и повторного присоединения к кластеру сообщение автоматически не очищается. Это сообщение появляется на вкладке Summary веб-клиента vSphere, и хост ESXi отображает треугольник уведомления, хотя аварийные сигналы не инициируются.
Это сообщение появляется на всех узлах в кластере vSAN, когда один или несколько узлов отключены для обслуживания и, следовательно, не взаимодействуют с остальной частью кластера, или когда существует допустимая проблема с связью кластера vSAN. В обычных условиях это сообщение автоматически сбрасывается после возобновления связи с хостами. Если это сообщение появляется на вкладке Сводка, в то время как все другие индикаторы сообщают, что сеть vSAN исправна, эта проблема может быть косметической.
Решение
Эта косметическая проблема устранена в VMware ESXi 6,0 Update 2, доступном на странице загрузки VMware
Чтобы устранить эту проблему, если обновление не требуется, используйте один из следующих вариантов:
Перезапустите агент управления VPXA на узлах vSAN. Это приводит к обновлению информации в vCenter Server и удалению сообщения.
Примечание. Перезапуск агента управления vCenter на хосте ESXi может привести к короткому прерыванию управления хостом. В крайних случаях хост может сразу же перейти в состояние "не отвечает" на сервере vCenter Server, или к ожидающим операциям, которые завершаются неуспешно, и их необходимо повторить.
Чтобы перезапустить агент управления VPXA (vCenter Server) на узлах узла ESXi кластера vSAN:
Включите SSH или ESXi Shell на каждом узле кластера vSAN.
Войдите на узел кластера vSAN с помощью SSH или ESXi Shell.
Перезапустите агент управления VPXA, выполнив эту команду # /etc/init.d/vpxa restart
Примечание. Подождите приблизительно одну минуту, прежде чем перейти к следующему хосту. Это позволяет одновременно обновлять информацию от каждого узла в vCenter Server.
Удалите узел из кластера vSAN и добавьте его повторно. Это вынуждает все узлы обновлять информацию о членстве в кластере и очищать сообщение.
Примечание. При попытке удаления и повторного добавления узла синхронизация данных не выполняется, когда узел находится в режиме обслуживания и находится вне кластера vSAN. При выборе опции «Гарантировать режим обслуживания специальных возможностей» некоторые объекты могут быть не защищены при выполнении обходного решения.
Для удаления узла из кластера vSAN и повторного добавления:
Выберите хост ESXi в кластере vSAN, который можно временно перевести в режим обслуживания
Примечание. VMware рекомендует выбрать наименее занятый/используемый хост.
В веб-клиенте vSphere щелкните правой кнопкой мыши узел ESXi и выберите "Перейти в режим обслуживания".
Примечания: Выберите параметры "Обеспечить доступность" или "Полное перемещение данных" для режима обслуживания vSAN. Если применимо, разрешите перенос отключенных виртуальных машин на остальные хосты ESXi.
3Удаление узла из кластера vSAN
Выберите хост.
Перетащите узел из кластера.
Поместите хост в объект центра обработки данных в хранилище сервера vCenter.
Примечание. После перемещения хоста в центр обработки данных подождите около двух минут.
Перетащите узел обратно в кластер vSAN.
После добавления узла обратно в кластер vSAN щелкните на него правой кнопкой мыши и выберите «Выход из режима обслуживания».
Примечание. Сообщение на остальных хостах должно быть понятным.
Примечание. Эти обходные пути успешно очищают сообщение. Однако при повторном появлении сообщения может потребоваться повторное применение обходного решения. Это сообщение может вновь появиться в таких случаях, как проблема с сетью, отказ/перезагрузка хоста или обслуживание хоста.
Алгоритм
– это набор четко сформулированных инструкций, который применяется для решения конкретной задачи. Эти задачи вы можете решать любым удобным для вас способом.
Это значит, что ваш метод, который вы используете для решения задачи, может отличаться от моего, но при этом мы оба должны получить один и тот же результат.
Так как способ решения одной и той же задачи может быть не один, то должен существовать и способ оценить эти решения или алгоритмы с точки зрения оптимальности и эффективности (время, которое требуется для запуска/выполнения вашего алгоритма, и общий объем потребляемой памяти).
Этот этап довольно важный для программистов. Его цель - помочь убедиться, что их приложения работают должным образом, и помочь написать чистый программный код.
И вот здесь на первый план выходит обозначение «О большое». «О большое» - это метрика, которая определяет эффективность алгоритма. Она позволяет оценить, сколько времени занимает выполнение программного кода с различными входными данными, и измерить, насколько эффективно этот программный код масштабируется по мере увеличения размера входных данных.
Что такое «О большое»?
«О большое» показывает сложность алгоритма для наихудшего случая. Для описания сложности алгоритма здесь используются алгебраические выражения.
«О большое» определяет время выполнения алгоритма, показывая, как будет меняться оптимальность алгоритма по мере увеличения размера входных данных. Однако этот показатель не расскажет вам о том, насколько быстро работает ваш алгоритм.
«О большое» измеряет эффективность и оптимальность алгоритма, основываясь на временной и пространственной сложности.
Что такое временная и пространственная сложность?
Один из самых основных факторов, который влияет на оптимальность и эффективность вашей программы – это оборудование, ОС и ЦП, которые вы используете.
Однако при анализе оптимальности алгоритма это не учитывается. Куда важнее учесть временную и пространственную сложность как функцию, которая зависит от размера входных данных.
Временная сложность алгоритма – это то, сколько времени потребуется для выполнения алгоритма в зависимости от размера входных данных. Аналогично пространственная сложность – это то, сколько пространства или памяти потребуется для выполнения алгоритма в зависимости от размера входных данных.
В данной статье мы рассмотрим временную сложность. Эта статья станет для вас своего рода шпаргалкой, которая поможет вам понять, как можно рассчитать временную сложность для любого алгоритма.
Почему временная сложность зависит от размера входных данных?
Для того, чтобы полностью понять, что же такое «зависимость от входных данных», представьте, что у вас есть некий алгоритм, который вычисляет сумму чисел, основываясь на ваших входных данных. Если вы ввели 4, то он сложит 1+2+3+4, и на выходе получится 10; если вы ввели 5, то на выходе будет 15 (то есть алгоритм сложил 1+2+3+4+5).
const calculateSum = (input) => {
let sum = 0;
for (let i = 0; i <= input; i++) {
sum += i;
}
return sum;
};
В приведенном выше фрагменте программного кода есть три оператора:
Давайте посмотрим на картинку выше. У нас есть три оператора. При этом, так как у нас есть цикл, то второй оператор будет выполняться, основываясь на размере входных данных, поэтому, если на входе алгоритм получает 4, то второй оператор будет выполняться четыре раза. А значит, в целом алгоритм выполнится шесть (4+2) раз.
Проще говоря, алгоритм будет выполняться input+2 раза; input может быть любым числом. Это говорит о том, что алгоритм выражается в терминах входных данных. Иными словами, это функция, которая зависит от размера входных данных.
Для понятия «О большое» есть шесть основных типов сложностей (временных и пространственных):
Постоянное время: O1
Линейное время: On
Логарифмическое время: On log n
Квадратичное время: On2
Экспоненциальное время: O2n
Факториальное время: On!
Прежде чем мы перейдем к рассмотрению всех этих временных сложностей, давайте посмотрим на диаграмму временной сложности «О большого».
Диаграмма временной сложности «О большого»
Диаграмма «О большого» - это асимптотические обозначение, которое используется для выражения сложности алгоритма или его оптимальности в зависимости от размера входных данных.
Данная диаграмма помогает программистам определить сценарий наихудшего случая, а также оценить время выполнения и объем требуемой памяти.
Следующий график иллюстрирует сложность «О большого»:
Глядя на приведенную выше диаграмму, можно определить, что O1 – постоянное время выполнения алгоритма, является наилучшим вариантом. Это означает, что ваш алгоритм обрабатывает только один оператор без какой-либо итерации. Дальше идет Olog n , что тоже является неплохим вариантом, и другие:
O1 – отлично/наилучший случай
Olog n – хорошо
On – удовлетворительно
On log n – плохо
On2, O2n, On! – ужасно/наихудший случай
Теперь вы имеете представление о различных временных сложностях, а также можете понять, какие из них наилучшие, хорошие или удовлетворительные, а какие плохие и наихудшие (плохих и наихудших временных сложностей следует избегать).
Следующий вопрос, который может прийти на ум: «какой алгоритм какую сложность имеет?» И это вполне логичный вопрос, ведь эта статья задумывалась как шпаргалка. ?
Когда ваши расчеты не зависят от размера входных данных, то это постоянная временная сложность - O1.
Когда размер входных данных уменьшается в два раза, например, при итерации, обработке рекурсии и т.д., то это логарифмическая временная сложность - Olog n .
Когда у вас один цикл в алгоритме, то это линейная временная сложность - On.
Когда у вас есть вложенные циклы, то есть цикл в цикле, то это квадратичная временная сложность - On2.
Когда скорость роста удваивается при каждом добавлении входных данных, то это экспоненциальная временная сложность - O2n.
Давайте перейдем к описанию временных сложностей. Для каждой будут приведены примеры. Отмечу, что в примерах я использовал JavaScript, но если вы понимаете принцип и что из себя представляет каждая временная сложность, то не имеет значения, какой язык программирования вы выберите.
Примеры временных сложностей «О большого»
Постоянное время: O1
Когда алгоритм не зависит от размера входных данных n, то говорят, что он имеет постоянную временную сложность порядка O1. Это значит, что время выполнения алгоритма всегда будет одним и тем же, независимо от размера входных данных.
Допустим, что задача алгоритма – вернуть первый элемент массива. Даже если массив состоит из миллиона элементов, временная сложность будет постоянной, если использовать следующий подход для решения задачи:
const firstElement = (array) => {
return array[0];
};
let score = [12, 55, 67, 94, 22];
console.log(firstElement(score)); // 12
Приведенная выше функция выполняет лишь один шаг, а это значит, что функция работает за постоянное время, и ее временная сложность O1.
Однако, как уже было сказано, разные программисты могут найти разные способы решения задачи. Например, другой программист может решить, что сначала надо пройти по массиву, а затем уже вернуть первый элемент:
const firstElement = (array) => {
for (let i = 0; i < array.length; i++) {
return array[0];
}
};
let score = [12, 55, 67, 94, 22];
console.log(firstElement(score)); // 12
Это просто пример – вряд ли кто-то будет решать эту задачу таким способом. Но здесь уже есть цикл, а значит алгоритм не будет выполняться за постоянное время, здесь в игру вступает линейное время с временной сложностью On.
Линейное время: On
Линейная временная сложность возникает, когда время работы алгоритма увеличивается линейно с размером входных данных. Когда функция имеет итерацию по входному значению n, то говорят, что она имеет временную сложность порядка On.
Допустим, алгоритм должен вычислить и вернуть факториал любого числа, которое вы введете. Это значит, что если вы введете число 5, то алгоритм должен выполнить цикл и умножить 1·2·3·4·5, а затем вывести результат – 120:
const calcFactorial = (n) => {
let factorial = 1;
for (let i = 2; i <= n; i++) {
factorial = factorial * i;
}
return factorial;
};
console.log(calcFactorial(5)); // 120
Тот факт, что время выполнения алгоритма зависит от размера входных данных, подразумевает наличие линейной временной сложности порядка On.
Логарифмическое время: Olog n
Это чем-то похоже на линейную временную сложность. Однако здесь время выполнения зависит не от размера входных данных, а от их половины. Когда размер входных данных уменьшается на каждой итерации или шаге, то говорят, что алгоритм имеет логарифмическую временную сложность.
Такой вариант считается вторым сверху списка лучших, так как ваша программа работает лишь с половиной входных данных. И при всем при этом, размер входных данных уменьшается с каждой итерацией.
Отличный пример – функция бинарного поиска, которая делит отсортированный массив, основываясь на искомом значения.
Допустим, что нам надо найти индекс определенного элемента в массиве с помощью алгоритма бинарного поиска:
const binarySearch = (array, target) => {
let firstIndex = 0;
let lastIndex = array.length - 1;
while (firstIndex <= lastIndex) {
let middleIndex = Math.floor((firstIndex + lastIndex) / 2);
if (array[middleIndex] === target) {
return middleIndex;
}
if (array[middleIndex] > target) {
lastIndex = middleIndex - 1;
} else {
firstIndex = middleIndex + 1;
}
}
return -1;
};
let score = [12, 22, 45, 67, 96];
console.log(binarySearch(score, 96));
Приведенный выше программный код демонстрирует бинарный поиск. Судя по нему, вы сначала получаете индекс среднего элемента вашего массива, дальше вы сравниваете его с искомым значением и, если они совпадают, то вы возвращаете этот индекс. В противном случае, если они не совпали, вы должны определить, искомое значение больше или меньше среднего, чтобы можно было изменить первый и последний индекс, тем самым уменьшив размер входных данных в два раза.
Так как на каждой такой итерации размер входных данных уменьшается в два раза, то данный алгоритм имеет логарифмическую временную сложность порядка Olog n .
Квадратичное время: On2
Когда в алгоритме присутствуют вложенные циклы, то есть цикл в цикле, то временная сложность уже становится квадратичной, и здесь нет ничего хорошего.
Представьте, что у вас есть массив из n элементов. Внешний цикл будет выполняться n раз, а внутрениий – n раз для каждой итерации внешнего цикла, и, соответственно, общее количество итераций составит n2. Если в массиве было 10 элементов, то количество итераций будет 100 (102).
Ниже приведен пример, где сравниваются элементы для того, чтобы можно было вывести индекс, когда найдутся два одинаковых:
const matchElements = (array) => {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
if (i !== j && array[i] === array[j]) {
return `Match found at ${i} and ${j}`;
}
}
}
return "No matches found ?";
};
const fruit = ["?", "?", "?", "?", "?", "?", "?", "?", "?", "?"];
console.log(matchElements(fruit)); // "Match found at 2 and 8"
В этом примере есть вложенный цикл, а значит, здесь будет квадратичная временная сложность порядка On2.
Экспоненциальное время: O2n
Экспоненциальная временная сложность появляется, когда скорость роста удваивается с каждым добавлением входных данных n, например, когда вы обходите все подмножества входных элементов. Каждый раз, когда единицу входных данных увеличивают на один, то количество итераций, которые выполняет алгоритм, увеличиваются в два раза.
Хороший пример – рекурсивная последовательность Фибоначчи. Допустим, дано число, и необходимо найти n-ый элемент последовательности Фибоначчи.
Последовательность Фибоначчи – это математическая последовательность, в которой каждое число является суммой двух предыдущих; первые два числа – 0 и 1. Третье число – 1, четвертое – 2, пятое – 3 и т.д. (0, 1, 1, 2, 3, 5, 8, 13, …).
Соответственно, если вы введете число 6, то выведется 6-й элемент в последовательности Фибоначчи – 8:
const recursiveFibonacci = (n) => {
if (n < 2) {
return n;
}
return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
};
console.log(recursiveFibonacci(6)); // 8
Приведенный выше алгоритм задает скорость роста, которая удваивается каждый раз, когда добавляются входные данные. А значит, данный алгоритм имеет экспоненциальную временную сложность порядка O2n.
Заключение
Из данной статьи вы узнали, что такое временная сложность, как определить оптимальность алгоритма с помощью «О большого», а также рассмотрели различные временные сложности с примерами.