По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
Предприятия, использующие различные бизнес-приложения, должны поддерживать конфиденциальность данных и предоставлять права доступа в соответствии с ролями пользователей во всей инфраструктуре. Сделать это достаточно сложно. SAML (Security Assertion Markup Language) значительно помогает в этом плане.
Давайте посмотрим, что же это такое и как оно работает, в чем его преимущества, чем оно отличается от SSO, а в чем оно похоже, и как оно помогает в проверке доступа к API для обеспечения максимального уровня безопасности.
Что такое SAML?
Основная работа SAML заключается в том, чтобы позволить IdP (поставщикам удостоверений - identity details providers) делиться учетными данными, связанными с аутентификацией, с соответствующими органами. Это открытый стандарт, который позволяет предоставить унифицированный доступ для всех видов приложений без ущерба для безопасности данных.
Вот еще несколько фактов, которые вы должны знать о SAML:
Он использует XML для завершения стандартного соединения между IdP и поставщиками услуг для обеспечения надежной связи.
Процесс аутентификации SAML подтверждает личность конечного пользователя, а авторизация SAML определяет, какие ресурсы должны быть доступны для пользователя.
Он проверяет SP (поставщиков услуг), IdP (поставщиков удостоверений) и конечных пользователей, если пользователь имеет право на требуемое действие.
Это стандарт OASIS.
Обеспечивает безопасный обмен данными.
Он поддерживает активацию SSO. Однако данная процедура требует подключения к внешнему поставщику удостоверений и совместного с ним использования XML-токенов.
Кратко о SSO (Single Sign-on – система однократного входа)
SSO считается одним из самых эффективных механизмов аутентификации и объединяет несколько экранов входа. Это значит, что вам не нужно самостоятельно входить в систему в своих приложениях. Вместо этого для приложений SaaS (Software as a Service) будет работать всего один набор данных для входа для всех ваших учетных записей.
Это обеспечивает более быстрый доступ к приложению, делает его более простым и подконтрольным. Это является ключевым аспектом IAM-стратегий компаний, стремящихся к беспрепятственной проверке доступа к приложениям и наилучшей реализации безопасности.
Включение SSO дает следующие возможности:
Надежные пароли, так как нет необходимости создавать несколько схожих паролей. Достаточно иметь один сложный и надежный пароль.
Пользователям не нужно запоминать различные пароли.
Простое использование MFA (Многофакторная аутентификация), которое проверяет несколько факторов, так как его активация в одной точке обеспечивает защиту различных приложений.
Политика быстрого повторного ввода пароля, поскольку у администраторов есть единственная точка применения политики.
Удобное внутренне управление учетными данными, поскольку SSO хранит пароли пользователей внутри и предоставляет IT-специалистам гораздо больший контроль над базой данных.
Мгновенное восстановление пароля пользователя, поскольку IT-команда должна работать над восстановлением одного пароля.
Аутентификация SAML – пошагово
Давайте рассмотрим всю процедуру в нескольких шагах.
Прежде всего, служба идентификации передает входные данные, связанные со входом пользователя в систему, поставщику услуг. Для бесперебойной передачи параметров SAML поставщикам услуг каждый конечный пользователь обязан один раз войти в систему через SSO.
Затем, SP связывается с IdP для подтверждения достоверности запроса. Этот процесс также требует предоставления согласия на настройку системы однократного входа SAML. Это гарантирует то, что для проверки личности и авторизации пользователя/запроса используются одни и те же параметры SAML.
Преимущества SAML
Данный подход имеет стандартный формат, поэтому он предоставляет предприятиям открытый подход, не зависящий от совместимости платформ и реализаций поставщиков.
Он использует слабосвязанные каталоги, что означает, что нет необходимости хранить и синхронизировать пользовательские данные с локальными каталогами.
Так как он поддерживает SSO, то конечные пользователи получат доступ к приложениям.
SAML позволяет предприятиям повторно использовать интеграции для регистрации/входа, сохраняя при этом тот же уровень безопасности. Это значительно сокращает расходы на управление аккаунтом.
Обязанность обслуживания удостоверений пользователей переносится на IdP, когда работает SAML. Это освобождает поставщиков услуг от лишних проблем, связанных с регистрацией и входом в систему.
Что такое SAML Assertion?
Выражаясь простым языком, это документ в формате XML, который содержит в себе информацию о статусе авторизации пользователя. Эта информация предоставляется IdP поставщику услуг.
Есть утверждения трех типов:
Authentication – это проверка личности пользователя, связанных с ней методов и сведения об отслеживании продолжительности сеанса.
Assigned обеспечивает успешную передачу SAML-токенов поставщику услуг. IdP и SP используют одни и те же атрибуты для подтверждения личности создателя запроса.
И последнее, утверждение типа Authorization-decision объясняет, где пользователю предоставляется доступ в соответствии с его запросом. Если будет отказано в доступе, то также будет предоставлена подробно описанная причина этого отказа.
Пример SAML
Ниже приведен самый простой пример того, как SAML обрабатывает свои операции:
Пусть конечный пользователь по имени Джон пытается получить доступ к бизнес-приложению в служебных целях.
Джон начинает сеанс с SSO и завершает часть процедуры проверки личности.
Zoho CRM запрашивает у IdP информацию о пользователе для подтверждения.
Программное средство SaaS получает доступ к результатам для завершения этапа проверки полномочий.
IdP отвечает по этому запросу в формате SAML. На нем будут цифровые подписи Джона. На основании сходства между идентифицированными данными, которые предоставил Джон и IdP, в ответном сообщении могут содержаться и другие сведения.
Программное средство SaaS получает ответ и предоставляет доступ или отказывает в доступе в соответствии с инструкциями IdP.
Если доступ был разрешен, то Джон может использовать свою учетную запись Zoho.
SAML vs SSO
SAML помогает в проверке личности пользователя и делает возможным использование системы однократного входа (SSO). SSO может существовать отдельно и позволяет конечным пользователям использовать различные приложения с унифицированными данными для входа. SSO может задействовать стандартные протоколы SAML при обмене информацией, поскольку у него нет собственным специальных протоколов. Помимо этого, он может использовать сторонние протоколы, такие как OpenID, для эффективной междоменной проверки личности пользователя. SAML имеет же широкий спектр собственных протоколов.
SAML vs oAuth2
Из-за сходства основного назначения SAML 2.0 и oAuth 2.0 часто принимают за одно и то же программное средство. Хотя они и имеют некоторое сходство, но они также имеют и различия в некоторых аспектах.
Сходства
И то, и другое необходимо для обеспечения безопасного взаимодействия приложений.
Оба поддерживают простое управление доступом и быструю интеграцию.
Различия
oAuth 2.0 больше уделяет внимание на авторизацию, тогда как SAML отдает приоритет аутентификации.
SAML основан на XML, а oAuth 2.0 – на JSON.
SAML поддерживает данные сеанса с помощью файлов cookie, в то время как oAuth использует вызовы API.
Аутентификация API с помощью SAML
Несмотря на то, что одним из самых распространенных вариантов применения SAML является поддержка проверка личности пользователя и включение SSO, он также может оказаться полезным для проверки подлинности запроса в API. Проверка прав доступа пользователя для проверки подлинности запроса является ключевой с точки зрения безопасности API и может быть проведена путем отправки SAML-запроса, который в свою очередь должен предусматривать следующее:
SAML подготавливает запрос аутентификации API на основе API-интерфейса.
Запрос должен содержать SAML-сообщение, которое может поддерживать процесс SSO, автоматически инициируемый IdP.
Очень важно, чтобы сообщение SAML-запроса основывалось на закодированном XML-документе с корневым элементом <Response>.
Тело запроса должно содержать текстовое наполнение, идентификаторы и область. Первые два аспекта являются обязательными, третий – нет.
Ответ SAML включает в себя access_token (маркер SAML, предоставляющий или запрещающий доступ), username (имя пользователя), expires_in, refresh_token и realm (область).
Заключение
SAML и SSO тесно связаны друг с другом. Это критически важно для обеспечения безопасности данных без каких-либо компромиссов. Надеюсь, эта статья поможет вам разобраться в теме и больше узнать об этих двух программных средствах.
Привет! Сегодня мы расскажем про то как настроить Site-To-Site IPSec VPN туннель между роутерами Cisco. Такие VPN туннели используются обеспечения безопасной передачи данных, голоса и видео между двумя площадками (например, офисами или филиалами). Туннель VPN создается через общедоступную сеть интернет и шифруется с использованием ряда продвинутых алгоритмов шифрования, чтобы обеспечить конфиденциальность данных, передаваемых между двумя площадками.
В этой статье будет показано, как настроить и настроить два маршрутизатора Cisco для создания постоянного безопасного туннеля VPN типа «сеть-сеть» через Интернет с использованием протокола IP Security (IPSec) . В рамках статьи мы предполагаем, что оба маршрутизатора Cisco имеют статический публичный IP-адрес.
ISAKMP (Internet Security Association and and Key Management Protocol) и IPSec необходимы для построения и шифрования VPN-туннеля. ISAKMP, также называемый IKE (Internet Key Exchange) , является протоколом согласования (negotiation protocol), который позволяет двум хостам договариваться о том, как создать сопоставление безопасности IPsec. Согласование ISAKMP состоит из двух этапов: фаза 1 и фаза 2.
Во время фазы 1 создается первый туннель, который защищает последующие сообщения согласования ISAKMP. Во время фазы 2 создается туннель, который защищает данные. Затем в игру вступает IPSec для шифрования данных с использованием алгоритмов шифрования и предоставляющий аутентификацию, шифрование и защиту от повторного воспроизведения.
Требования к IPSec VPN
Чтобы упростить понимание настройки разделим его на две части:
Настройка ISAKMP (Фаза 1 ISAKMP)
Настройка IPSec (Фаза 2 ISAKMP, ACL, Crypto MAP)
Делать будем на примере, который показан на схеме – два филиала, оба маршрутизатора филиалов подключаются к Интернету и имеют статический IP-адрес, назначенный их провайдером. Площадка №1 имеет внутреннею подсеть 10.10.10.0/24, а площадка №2 имеет подсеть 20.20.20.0/24. Цель состоит в том, чтобы безопасно соединить обе сети LAN и обеспечить полную связь между ними без каких-либо ограничений.
Настройка ISAKMP (IKE) - ISAKMP Phase 1
IKE нужен только для установления SA (Security Association) для IPsec. Прежде чем он сможет это сделать, IKE должен согласовать отношение SA (ISAKMP SA) с одноранговым узлом (peer).
Начнем с настройки маршрутизатора R1 первой площадки. Первым шагом является настройка политики ISAKMP Phase 1:
R1(config)# crypto isakmp policy 1
R1(config-isakmp)# encr 3des
R1(config-isakmp)# hash md5
R1(config-isakmp)# authentication pre-share
R1(config-isakmp)# group 2
R1(config-isakmp)# lifetime 86400
Приведенные выше команды означают следующее:
3DES - метод шифрования, который будет использоваться на этапе 1
MD5 - алгоритм хеширования
Pre-Share - использование предварительного общего ключа (PSK) в качестве метода проверки подлинности
Group 2 - группа Диффи-Хеллмана, которая будет использоваться
86400 - время жизни ключа сеанса. Выражается либо в килобайтах (сколько трафика должно пройти до смены ключа), либо в секундах. Значение установлено по умолчанию.
Мы должны отметить, что политика ISAKMP Phase 1 определяется глобально. Это означает, что если у нас есть пять разных удаленных площадок и настроено пять разных политик ISAKMP Phase 1 (по одной для каждого удаленного маршрутизатора), то, когда наш маршрутизатор пытается согласовать VPN-туннель с каждой площадкой, он отправит все пять политик и будет использовать первое совпадение, которое принято обоими сторонами.
Далее мы собираемся определить Pre-Shared ключ для аутентификации с нашим партнером (маршрутизатором R2) с помощью следующей команды:
R1(config)# crypto isakmp key merionet address 1.1.1.2
Pre-Shared ключ партнера установлен на merionet, а его публичный IP-адрес - 1.1.1.2. Каждый раз, когда R1 пытается установить VPN-туннель с R2 (1.1.1.2), будет использоваться этот ключ.
Настройка IPSec – 4 простых шага
Для настройки IPSec нам нужно сделать следующее:
Создать расширенный ACL
Создать IPSec Transform
Создать криптографическую карту (Crypto Map)
Применить криптографическую карту к общедоступному (public) интерфейсу
Давайте рассмотрим каждый из вышеперечисленных шагов.
Шаг 1: Создаем расширенный ACL
Нам нужно создать расширенный access-list (про настройку Extended ACL можно прочесть в этой статье) и в нем определить какой траффик мы хотим пропускать через VPN-туннель. В этом примере это будет трафик из одной сети в другую с 10.10.10.0/24 по 20.20.20.0/24. Иногда такие списки называют crypto access-list или interesting traffic access-list.
R1(config)# ip access-list extended VPN-TRAFFIC
R1(config-ext-nacl)# permit ip 10.10.10.0 0.0.0.255 20.20.20.0 0.0.0.255
Шаг 2: Создаем IPSec Transform
Следующим шагом является создание набора преобразования (Transform Set), используемого для защиты наших данных. Мы назвали его TS.
R1(config)# crypto ipsec transform-set TS esp-3des esp-md5-hmac
Приведенная выше команда определяет следующее:
ESP-3DES - метод шифрования
MD5 - алгоритм хеширования
Шаг 3: Создаем Crypto Map
Crypto Map является последнем этапом нашей настройки и объединяет ранее заданные конфигурации ISAKMP и IPSec:
R1(config)# crypto map CMAP 10 ipsec-isakmp
R1(config-crypto-map)# set peer 1.1.1.2
R1(config-crypto-map)# set transform-set TS
R1(config-crypto-map)# match address VPN-TRAFFIC
Мы назвали нашу криптографическую карту CMAP. Тег ipsec-isakmp сообщает маршрутизатору, что эта криптографическая карта является криптографической картой IPsec. Хотя в этой карте (1.1.1.2) объявлен только один пир, существует возможность иметь несколько пиров.
Шаг 4: Применяем криптографическую карту к общедоступному интерфейсу
Последний шаг - применить криптографическую карту к интерфейсу маршрутизатора, через который выходит траффик. Здесь исходящим интерфейсом является FastEthernet 0/1.
R1(config)# interface FastEthernet0/1
R1(config- if)# crypto map CMAP
Обратите внимание, что интерфейсу можно назначить только одну криптокарту.
Как только мы применим криптографическую карту к интерфейсу, мы получаем сообщение от маршрутизатора, подтверждающее, что isakmp включен: “ISAKMP is ON”.
На этом этапе мы завершили настройку IPSec VPN на маршрутизаторе Площадки 1.
Теперь перейдем к маршрутизатору Площадки 2 для завершения настройки VPN. Настройки для R2 идентичны, с отличиями лишь в IP-адресах пиров и ACL.
R2(config)# crypto isakmp policy 1
R2(config-isakmp)# encr 3des
R2(config-isakmp)# hash md5
R2(config-isakmp)# authentication pre-share
R2(config-isakmp)# group 2
R2(config-isakmp)# lifetime 86400
R2(config)# crypto isakmp key merionet address 1.1.1.1
R2(config)# ip access-list extended VPN-TRAFFIC
R2(config-ext-nacl)# permit ip 20.20.20.0 0.0.0.255 10.10.10.0 0.0.0.255
R2(config)# crypto ipsec transform-set TS esp-3des esp-md5-hmac
R2(config)# crypto map CMAP 10 ipsec-isakmp
R2(config-crypto-map)# set peer 1.1.1.1
R2(config-crypto-map)# set transform-set TS
R2(config-crypto-map)# match address VPN-TRAFFIC
R2(config)# interface FastEthernet0/1
R2(config- if)# crypto map CMAP
Трансляция сетевых адресов (NAT) и VPN-туннели IPSec
В реальной схеме трансляция сетевых адресов (NAT), скорее всего, будет настроена для предоставления доступа в интернет внутренним хостам. При настройке VPN-туннеля типа «Site-To-Site» обязательно нужно указать маршрутизатору не выполнять NAT (deny NAT) для пакетов, предназначенных для удаленной сети VPN.
Это легко сделать, вставив оператор deny в начало списков доступа NAT, как показано ниже:
Для первого маршрутизатора:
R1(config)# ip nat inside source list 100 interface fastethernet0/1 overload
R1(config)# access-list 100 deny ip 10.10.10.0 0.0.0.255 20.20.20.0 0.0.0.255
R1(config)# access-list 100 permit ip 10.10.10.0 0.0.0.255 any
Для второго маршрутизатора:
R2(config)# ip nat inside source list 100 interface fastethernet0/1 overload
R2(config)# access-list 100 deny ip 20.20.20.0 0.0.0.255 10.10.10.0 0.0.0.255
R2(config)# access-list 100 permit ip 20.20.20.0 0.0.0.255 any
Инициализация и проверка VPN-туннеля IPSec
К этому моменту мы завершили нашу настройку, и VPN-туннель готов к запуску. Чтобы инициировать VPN-туннель, нам нужно заставить один пакет пройти через VPN, и этого можно достичь, отправив эхо-запрос от одного маршрутизатора к другому:
R1# ping 20.20.20.1 source fastethernet0/0
Type escape sequence to abort.
Sending 5, 100-byte ICMP Echos to 20.20.20.1, timeout is 2 seconds:
Packet sent with a source address of 10.10.10.1
.!!!!
Success rate is 80 percent (4/5), round-trip min/avg/max = 44/47/48 ms
Первое эхо-сообщение icmp (ping) получило тайм-аут, но остальные получили ответ, как и ожидалось. Время, необходимое для запуска VPN-туннеля, иногда превышает 2 секунды, что приводит к истечению времени ожидания первого пинга.
Чтобы проверить VPN-туннель, используйте команду show crypto session:
R1# show crypto session
Crypto session current status
Interface: FastEthernet0/1
Session status: UP-ACTIVE
Peer: 1.1.1.2 port 500
IKE SA: local 1.1.1.1/500 remote 1.1.1.2/500 Active
IPSEC FLOW: permit ip 10.10.10.0/255.255.255.0 20.20.20.0/255.255.255.0
Active SAs: 2, origin: crypto map
Готово! Мы только что успешно подняли Site-To-Site IPSEC VPN туннель между двумя маршрутизаторами Cisco!
Алгоритм
– это набор четко сформулированных инструкций, который применяется для решения конкретной задачи. Эти задачи вы можете решать любым удобным для вас способом.
Это значит, что ваш метод, который вы используете для решения задачи, может отличаться от моего, но при этом мы оба должны получить один и тот же результат.
Так как способ решения одной и той же задачи может быть не один, то должен существовать и способ оценить эти решения или алгоритмы с точки зрения оптимальности и эффективности (время, которое требуется для запуска/выполнения вашего алгоритма, и общий объем потребляемой памяти).
Этот этап довольно важный для программистов. Его цель - помочь убедиться, что их приложения работают должным образом, и помочь написать чистый программный код.
И вот здесь на первый план выходит обозначение «О большое». «О большое» - это метрика, которая определяет эффективность алгоритма. Она позволяет оценить, сколько времени занимает выполнение программного кода с различными входными данными, и измерить, насколько эффективно этот программный код масштабируется по мере увеличения размера входных данных.
Что такое «О большое»?
«О большое» показывает сложность алгоритма для наихудшего случая. Для описания сложности алгоритма здесь используются алгебраические выражения.
«О большое» определяет время выполнения алгоритма, показывая, как будет меняться оптимальность алгоритма по мере увеличения размера входных данных. Однако этот показатель не расскажет вам о том, насколько быстро работает ваш алгоритм.
«О большое» измеряет эффективность и оптимальность алгоритма, основываясь на временной и пространственной сложности.
Что такое временная и пространственная сложность?
Один из самых основных факторов, который влияет на оптимальность и эффективность вашей программы – это оборудование, ОС и ЦП, которые вы используете.
Однако при анализе оптимальности алгоритма это не учитывается. Куда важнее учесть временную и пространственную сложность как функцию, которая зависит от размера входных данных.
Временная сложность алгоритма – это то, сколько времени потребуется для выполнения алгоритма в зависимости от размера входных данных. Аналогично пространственная сложность – это то, сколько пространства или памяти потребуется для выполнения алгоритма в зависимости от размера входных данных.
В данной статье мы рассмотрим временную сложность. Эта статья станет для вас своего рода шпаргалкой, которая поможет вам понять, как можно рассчитать временную сложность для любого алгоритма.
Почему временная сложность зависит от размера входных данных?
Для того, чтобы полностью понять, что же такое «зависимость от входных данных», представьте, что у вас есть некий алгоритм, который вычисляет сумму чисел, основываясь на ваших входных данных. Если вы ввели 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.
Заключение
Из данной статьи вы узнали, что такое временная сложность, как определить оптимальность алгоритма с помощью «О большого», а также рассмотрели различные временные сложности с примерами.