По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
Давайте для начала разберемся, что же такое Composer. Представленное программное обеспечение является менеджером пакетных зависимостей, разработанный для облегчения загрузки, а также установки различных PHP библиотек для вашего проекта. К примеру, используя менеджер пакетов, вы можете с легкостью добавить различные библиотеки к вашему проекту, разработкой которого вы занимаетесь, а также очень легко выполнять развертывание иных проектов, каковые имеют при себе документ composer.json.
Composer.json является текстовым документов, который содержит библиотеки, каковые использует проект. Кроме того, Composer используется возможно использовать для установки различных фреймворков PHP, а также CMS.
Данный менеджер пакетов представляет собой типичный PHP-скрипт, то есть программный продукт, разработанный на языке PHP.
Главной целью данного программного продукта является предоставление удобного инструмента для веб-разработчиков, с помощью какового он с легкостью может выполнять загрузку, а также установку библиотек в проект, выполнять их обновление, и, при необходимости, деинсталляцию. С помощью менеджера пакетов можно выполнять все перечисленные выше действия с помощью нескольких команд.
Composer при скачивании библиотек выполняет не только установку, но также устанавливает зависимости, от которых они уже могут зависеть. Допустим, вы загрузили некий пакет, который имеет зависимость от нескольких пакетов, и так далее. Данный менеджер пакетов автоматически выполнит установку.
Представленный PHP-скрипт создает в корне проекта специальную папку Vendor, в которую уже и выполняется установку сторонних библиотек. Помимо этого, также создается документ autoload.php с помощью которого происходит интеграция пакетов в проект.
Помимо перечисленных выше документов, при установке сторонних пакетов, также создается дополнительный документ composer.lock. Если же вышеописанный файл composer.json выполняет роль описания и требований версий библиотек, тогда composer.lock содержит в себе сами версии библиотек, каковые установились юзером.
Основной целью документа composer.lock является оставить среду, в каковой был разработан и протестирован проект без каких-либо изменений.
Работать с менеджером пакетов возможно с помощью консоли либо терминала, используя некоторые команды.
Как установить менеджер пакетов на OpenServer (Windows)
OpenServer по умолчанию содержит в себе Composer. Это будет зависеть от версии PHP.
Для того, чтобы работать с данным менеджером пакетов, потребуется его собственная консоль, которую возможно открыть с помощью нажатия ПКМ на раздел Открыть сервер, и обнаружить пункт консольного меню в списке меню.
Чтобы убедиться в том, что Composer включен, достаточно ввести команду Composer, и для вас отобразиться информация о вашей версии.
Если же вы получите уведомление, что ваша версия уже устарела, вы можете обновить ее с помощью специальной команды composer self-update.
Как установить менеджер пакетов на хостинг?
Чтобы установить Composer на хостинг-сервис, просто скачайте эту программу и загрузите ее в корневой каталог проекта, например, по FTP.
Команды на удаленном сервере обычно выполняются через SSH. По умолчанию на виртуальном хостинге этот сетевой протокол отключен. Чтобы включить его, вам нужно найти соответствующий элемент на панели управления, открыть его и нажать на кнопку Включить SSH внутри него.
Если на вашем компьютере установлена операционная система Windows 10, тогда SSH-клиент автоматически будет добавлен в систему. А это может означать, что для использования команд над управлением удаленного сервера, вам не потребуется ничего устанавливать, так как можно использовать Windows PowerShell либо командную строку.
Первая часть тут
Как только изменение в топологии сети было обнаружено, оно должно быть каким-то образом распределено по всем устройствам, участвующим в плоскости управления. Каждый элемент в топологии сети может быть описан как:
Канал или граница, включая узлы или достижимые места назначения, прикрепленные к этому каналу.
Устройство или узел, включая узлы, каналы и доступные места назначения, подключенные к этому устройству.
Этот довольно ограниченный набор терминов может быть помещен в таблицу или базу данных, часто называемую таблицей топологии или базой данных топологии. Таким образом, вопрос о распределении изменений в топологии сети на все устройства, участвующие в плоскости управления, можно описать как процесс распределения изменений в определенных строках в этой таблице или базе данных по всей сети.
Способ, которым информация распространяется по сети, конечно, зависит от конструкции протокола, но обычно используются три вида распространения: поэтапное (hop-by-hop) распространение, лавинное (flooded) распространение и централизованное (centralized) хранилище некоторого вида.
Лавинное (flooded) распространение.
При лавинной рассылке каждое устройство, участвующее в плоскости управления, получает и сохраняет копию каждой части информации о топологии сети и доступных местах назначения. Хотя существует несколько способов синхронизации базы данных или таблицы, в плоскостях управления обычно используется только один: репликация на уровне записи. Рисунок 6 иллюстрирует это.
На рисунке 6 каждое устройство будет рассылать известную ему информацию ближайшим соседям, которые затем повторно рассылают информацию своим ближайшим соседу. Например, A знает две специфические вещи о топологии сети: как достичь 2001: db8: 3e8: 100 :: / 64 и как достичь B. A передает эту информацию в B, который, в свою очередь, передает эту информацию в C. Каждое устройство в сети в конечном итоге получает копию всей доступной топологической информации; A, B и C имеют синхронизированные базы данных топологии (или таблицы).
На рисунке 6 связь C с D показана как элемент в базе данных. Не все плоскости управления будут включать эту информацию. Вместо этого C может просто включать подключение к диапазону адресов 2001: db8: 3e8: 102 :: / 64 (или подсети), который содержит адрес D.
Примечание. В более крупных сетях невозможно уместить все описание подключений устройства в один пакет размером с MTU, и для обеспечения актуальности информации о подключении необходимо регулярно задерживать время ожидания и повторно загружать данные.
Интересная проблема возникает в механизмах распространения Flooding рассылки, которые могут вызывать временные петли маршрутизации, называемые microloops. Рисунок 7 демонстрирует эту ситуацию. На рисунке 7, предположим, что канал [E, D] не работает. Рассмотрим следующую цепочку событий, включая примерное время для каждого события:
Старт: A использует E, чтобы добраться до D; C использует D, чтобы добраться до E.
100 мс: E и D обнаруживают сбой связи.
500 мс: E и D рассылают информацию об изменении топологии на C и A.
750 мс: C и A получают обновленную информацию о топологии.
1000 мс: E и D пересчитывают свои лучшие пути; E выбирает A как лучший путь для достижения D, D выбирает C как лучший путь для достижения E.
1,250 мс: лавинная рассылка A и C информации об изменении топологии на B.
1400 мс: A и C пересчитывают свои лучшие пути; A выбирает B для достижения D, C выбирает B для достижения E.
1500 мс: B получает обновленную информацию о топологии.
2,000 мс: B пересчитывает свои лучшие пути; он выбирает C, чтобы достичь D, и A, чтобы достичь E.
Хотя время и порядок могут незначительно отличаться в каждой конкретной сети, порядок обнаружения, объявления и повторных вычислений почти всегда будет следовать аналогичной схеме. В этом примере между этапами 5 и 7 образуется микропетля; в течение 400 мс, A использует E для достижения D, а E использует A для достижения D. Любой трафик, входящий в кольцо в A или D в течение времени между пересчетом E лучшего пути к D и пересчетом A лучшего пути к D будет петлей. Одним из решений этой проблемы является предварительное вычисление альтернативных вариантов без петель или удаленных альтернатив без петель.
Hop by Hop
При поэтапном распределении каждое устройство вычисляет локальный лучший путь и отправляет только лучший путь своим соседям. Рисунок 8 демонстрирует это.
На рисунке 8 каждое устройство объявляет информацию о том, что может достигнуть каждого из своих соседей. D, например, объявляет о достижимости для E, а B объявляет о доступности для C, D и E для A. Интересно рассмотреть, что происходит, когда A объявляет о своей доступности для E через канал на вершине сети. Как только E получит эту информацию, у него будет два пути к B, например: один через D и один через A. Таким же образом у A будет два пути к B: один напрямую к B, а другой через E. Любой из алгоритмов кратчайшего пути, рассмотренные в предыдущих статьях, могут определить, какой из этих путей использовать, но возможно ли формирование микропетель с помощью лавинного механизма распределения?
Рассмотрим:
E выбирает путь через A, чтобы добраться до B.
Канал [A, B] не работает.
A обнаруживает этот сбой и переключается на путь через E.
Затем A объявляет этот новый путь к E.
E получает информацию об измененной топологии и вычисляет новый лучший путь через D.
В промежутке между шагами 3 и 5 А будет указывать на Е как на свой лучший путь к В, в то время как Е будет указывать на А как на свой лучший путь к В—микропетля. Большинство распределительных систем hop-by-hop решают эту проблему с помощью split horizon или poison reverse.
Определены они следующим образом:
Правило split horizon гласит: устройство не должно объявлять о доступности к пункту назначения, который он использует для достижения пункта назначения.
Правило poison reverse гласит: устройство должно объявлять пункты назначения по отношению к соседнему устройству, которое оно использует, чтобы достичь пункта назначения с бесконечной метрикой.
Если разделение горизонта (split horizon) реализованный на рисунке 8, E не будет объявлять о достижимости для B, поскольку он использует путь через A для достижения B. В качестве альтернативы E может отравить путь к B через A, что приведет к тому, что A не будет иметь пути через E к B.
Централизованное Хранилище.
В централизованной системе каждое сетевое устройство сообщает информацию об изменениях топологии и достижимости контроллеру или, скорее, некоторому набору автономных служб и устройств, действующих в качестве контроллера. В то время как централизация часто вызывает идею единого устройства (или виртуального устройства), которому передается вся информация и который передает правильную информацию для пересылки всем устройствам обработки пакетов в сети, это чрезмерное упрощение того, что на самом деле означает централизованная плоскость управления. Рисунок 9 демонстрирует это.
На рисунке 9, когда канл между D и F не работает:
D и F сообщают об изменении топологии контроллеру Y.
Y пересылает эту информацию другому контроллеру X.
Y вычисляет лучший путь к каждому месту назначения без канала [D, F] и отправляет его каждому затронутому устройству в сети.
Каждое устройство устанавливает эту новую информацию о пересылке в свою локальную таблицу.
Конкретный пример шага 3 - Y вычисляет следующий лучший путь к E без канала [D, F] и отправляет его D для установки в его локальной таблице пересылки. Могут ли микропетли образовываться в централизованной плоскости управления?
Базы данных в X и Y должны быть синхронизированы, чтобы оба контроллера вычисляли одинаковые пути без петель в сети
Синхронизация этих баз данных повлечет за собой те же проблемы и (возможно) использование тех же решений, что и решения, обсуждавшиеся до сих пор в этой статье.
Подключенным устройствам потребуется некоторое время, чтобы обнаружить изменение топологии и сообщить об этом контроллеру.
Контроллеру потребуется некоторое время, чтобы вычислить новые пути без петель.
Контроллеру потребуется некоторое время, чтобы уведомить затронутые устройства о новых путях без петель в сети.
Во время временных интервалов, описанных здесь, сеть все еще может образовывать микропетли. Централизованная плоскость управления чаще всего переводится в плоскость управления не запущенными устройствами переадресации трафика. Хотя они могут казаться радикально разными, централизованные плоскости управления на самом деле используют многие из тех же механизмов для распределения топологии и достижимости, а также те же алгоритмы для вычисления безцикловых путей через сеть, что и распределенные плоскости управления.
Плоскости сегментирования и управления.
Одна интересная идея для уменьшения состояния, переносимого на любое отдельное устройство, независимо от того, используется ли распределенная или централизованная плоскость управления, заключается в сегментировании информации в таблице топологии (или базе данных). Сегментация-это разделение информации в одной таблице на основе некоторого свойства самих данных и хранение каждого полученного фрагмента или фрагмента базы данных на отдельном устройстве. Рисунок 10 демонстрирует это.
В сети на рисунке 10 предположим, что оба контроллера, X и Y, имеют информацию о топологии для всех узлов (устройств) и ребер (каналов) в сети. Однако для масштабирования размера сети доступные места назначения были разделены на два контроллера. Существует множество возможных схем сегментирования - все, что может разделить базу данных (или таблицу) на части примерно одинакового размера, будет работать. Часто используется хеш, так как хеши можно быстро изменить на каждом устройстве, где хранится сегмент, чтобы сбалансировать размеры сегментов.
В этом случае предположим, что схема сегментирования немного проще: это диапазон IP-адресов. В частности, на рисунке представлены два диапазона IP-адресов: 2001: db8: 3e8: 100 :: / 60, который содержит от 100 :: / 64 до 10f :: / 64; и 2001: db8: 3e8: 110 :: / 60, который содержит от 110 :: / 64 до 11f :: / 64. Каждый из этих диапазонов адресов разделен на один контроллер; X будет содержать информацию о 2001: db8: 3e8: 100 :: / 60, а Y будет содержать информацию о 2001: db8: 3e8: 110 :: / 64. Не имеет значения, где эти доступные пункты назначения подключены к сети. Например, информация о том, что 2001: db8: 3e8: 102 :: / 64 подключен к F, будет храниться в контроллере X, а информация о том, что 2001: db8: 3e8: 110 :: / 64 подключен к A, будет храниться на контроллере Y. Чтобы получить информацию о доступности для 2001: db8: 3e8: 102 :: / 64, Y потребуется получить информацию о том, где этот пункт назначения соединен с X. Это будет менее эффективно с точки зрения вычисления кратчайших путей, но он будет более эффективным с точки зрения хранения информации, необходимой для вычисления кратчайших путей. Фактически, возможно, если информация хранится правильно (а не тривиальным способом, используемым в этом примере), чтобы несколько устройств вычислили разные части кратчайшего пути, а затем обменивались только результирующим деревом друг с другом. Это распределяет не только хранилище, но и обработку.
Существует несколько способов, с помощью которых информация о плоскости управления может быть разделена, сохранена и, когда вычисления выполняются через нее, чтобы найти набор путей без петель через сеть.
Согласованность, доступность и возможность разделения.
Во всех трех системах распределения, обсуждаемых в этой статье, - лавинной, поэтапной и централизованных хранилищ - возникает проблема микропетель. Протоколы, реализующие эти методы, имеют различные системы, такие как разделение горизонта и альтернативы без петель, чтобы обходить эти микропетли, или они позволяют микропетлям появляться, предполагая, что последствия будут небольшими для сети. Существует ли объединяющая теория или модель, которая позволит инженерам понять проблемы, связанные с распределением данных по сети, и различные сопутствующие компромиссы?
Есть: теорема CAP.
В 2000 году Эрик Брюер, занимаясь как теоретическими, так и практическими исследованиями, постулировал, что распределенная база данных обладает тремя качествами: Согласованностью, Доступностью и устойчивость к разделению (Consistency, Accessibility Partition tolerance-CAP). Между этими тремя качествами всегда есть компромисс, так что вы можете выбрать два из трех в любой структуре системы. Эта гипотеза, позже доказанная математически, теперь известна как теорема CAP. Эти три термина определяются как:
Согласованность: Каждый считыватель видит согласованное представление содержимого базы данных. Если какое-то устройство С записывает данные в базу данных за несколько мгновений до того, как два других устройства, А и В, прочитают данные из базы данных, оба считывателя получат одну и ту же информацию. Другими словами, нет никакой задержки между записью базы данных и тем, что оба считывателя, А и В, могут прочитать только что записанную информацию.
Доступность: каждый считыватель имеет доступ к базе данных при необходимости (почти в реальном времени). Ответ на чтение может быть отложен, но каждое чтение будет получать ответ. Другими словами, каждый считыватель всегда имеет доступ к базе данных. Не существует времени, в течение которого считыватель получил бы ответ «сейчас вы не можете запросить эту базу данных».
Устойчивость к разделению: возможность копирования или разделения базы данных на несколько устройств.
Проще изучить теорему CAP в небольшой сети. Для этого используется рисунок 11.
Предположим, что A содержит единственную копию базы данных, к которой должны иметь доступ как C, так и D. Предположим, что C записывает некоторую информацию в базу данных, а затем сразу же после, C и D считывают одну и ту же информацию. Единственная обработка, которая должна быть, чтобы убедиться, что C и D получают одну и ту же информацию, - это A. Теперь реплицируйте базу данных, чтобы была копия на E и еще одна копия на F. Теперь предположим, что K записывает в реплику на E, а L читает из реплики на F. Что же будет?
F может вернуть текущее значение, даже если это не то же самое значение, что только что записал К. Это означает, что база данных возвращает непоследовательный ответ, поэтому согласованность была принесена в жертву разделению базы данных.
Если две базы данных синхронизированы, ответ, конечно, в конечном итоге одинаковым, но потребуется некоторое время, чтобы упаковать изменение (упорядочить данные), передать его в F и интегрировать изменение в локальную копию F. F может заблокировать базу данных или определенную часть базы данных, пока выполняется синхронизация. В этом случае, когда L читает данные, он может получить ответ, что запись заблокирована. В этом случае доступность теряется, но сохраняется согласованность и разбиение базы данных.
Если две базы данных объединены, то согласованность и доступность могут быть сохранены за счет разделения.
Невозможно решить эту проблему, чтобы все три качества были сохранены, из-за времени, необходимого для синхронизации информации между двумя копиями базы данных. Та же проблема актуальна и для сегментированной базы данных.
Как это применимо к плоскости управления? В распределенной плоскости управления база данных, из которой плоскость управления черпает информацию для расчета путей без петель, разделена по всей сети. Кроме того, база данных доступна для чтения локально в любое время для расчета путей без петель. Учитывая разделение и доступность, необходимые для распределенной базы данных, используемой в плоскости управления, следует ожидать, что непротиворечивость пострадает - и это действительно так, что приводит к микропетлям во время конвергенции. Централизованная плоскость управления не «решает» эту проблему. Централизованная плоскость управления, работающая на одном устройстве, всегда будет согласованной, но не всегда будет доступной, а отсутствие разделения будет представлять проблему для устойчивости сети.
Алгоритм
– это набор четко сформулированных инструкций, который применяется для решения конкретной задачи. Эти задачи вы можете решать любым удобным для вас способом.
Это значит, что ваш метод, который вы используете для решения задачи, может отличаться от моего, но при этом мы оба должны получить один и тот же результат.
Так как способ решения одной и той же задачи может быть не один, то должен существовать и способ оценить эти решения или алгоритмы с точки зрения оптимальности и эффективности (время, которое требуется для запуска/выполнения вашего алгоритма, и общий объем потребляемой памяти).
Этот этап довольно важный для программистов. Его цель - помочь убедиться, что их приложения работают должным образом, и помочь написать чистый программный код.
И вот здесь на первый план выходит обозначение «О большое». «О большое» - это метрика, которая определяет эффективность алгоритма. Она позволяет оценить, сколько времени занимает выполнение программного кода с различными входными данными, и измерить, насколько эффективно этот программный код масштабируется по мере увеличения размера входных данных.
Что такое «О большое»?
«О большое» показывает сложность алгоритма для наихудшего случая. Для описания сложности алгоритма здесь используются алгебраические выражения.
«О большое» определяет время выполнения алгоритма, показывая, как будет меняться оптимальность алгоритма по мере увеличения размера входных данных. Однако этот показатель не расскажет вам о том, насколько быстро работает ваш алгоритм.
«О большое» измеряет эффективность и оптимальность алгоритма, основываясь на временной и пространственной сложности.
Что такое временная и пространственная сложность?
Один из самых основных факторов, который влияет на оптимальность и эффективность вашей программы – это оборудование, ОС и ЦП, которые вы используете.
Однако при анализе оптимальности алгоритма это не учитывается. Куда важнее учесть временную и пространственную сложность как функцию, которая зависит от размера входных данных.
Временная сложность алгоритма – это то, сколько времени потребуется для выполнения алгоритма в зависимости от размера входных данных. Аналогично пространственная сложность – это то, сколько пространства или памяти потребуется для выполнения алгоритма в зависимости от размера входных данных.
В данной статье мы рассмотрим временную сложность. Эта статья станет для вас своего рода шпаргалкой, которая поможет вам понять, как можно рассчитать временную сложность для любого алгоритма.
Почему временная сложность зависит от размера входных данных?
Для того, чтобы полностью понять, что же такое «зависимость от входных данных», представьте, что у вас есть некий алгоритм, который вычисляет сумму чисел, основываясь на ваших входных данных. Если вы ввели 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.
Заключение
Из данной статьи вы узнали, что такое временная сложность, как определить оптимальность алгоритма с помощью «О большого», а также рассмотрели различные временные сложности с примерами.