Кто такие сложные люди? Что означает сложность.

СЛОЖНОСТЬ, сложности, мн. нет, жен. отвлеч. сущ. к сложный. Сложность вопроса. Сложность дела. Сложность международного положения. ❖ В общей сложности принимая во внимание всё, в итоге, в сумме, в целом. В общей сложности, работы осталось еще на… … Толковый словарь Ушакова

сложность - СЛОЖНОСТЬ, замысловатость, запутанность, трудность, устар. многосложность, разг. каверзность, разг. хитроумие СЛОЖНЫЙ, головоломный, замысловатый, запутанный, неоднолинейный, непростой, трудный, хитросплетенный, хитроумный, устар.… … Словарь-тезаурус синонимов русской речи

СЛОЖНОСТЬ, и, жен. 1. см. сложный. 2. обычно мн. Трудность, осложняющее обстоятельство. Возникли сложности с оформлением. Толковый словарь Ожегова. С.И. Ожегов, Н.Ю. Шведова. 1949 1992 … Толковый словарь Ожегова

сложность - 1. Составленность из нескольких частей; многообразность по составу входящих частей и связей между ними. 2. Трудность, запутанность. Противоположное понятие простота. Словарь практического психолога. М.: АСТ, Харвест. С. Ю. Головин. 1998 … Большая психологическая энциклопедия

сложность - — Тематики защита информации EN difficulty … Справочник технического переводчика

сложность - большая сложность наибольшая сложность огромное сложность чрезвычайная сложность … Словарь русской идиоматики

сложность - sudėtingumas statusas T sritis radioelektronika atitikmenys: angl. complexity vok. Komplexität, f rus. сложность, f pranc. complexité, f … Radioelektronikos terminų žodynas

сложность - 3.8 сложность (complexity): Свойство системы или компонента, имеющих устройство, исполнение или поведение, трудные для понимания или верификации. Источник: ГОСТ Р МЭК 61513 2011: Атомные станции. Системы контроля и… … Словарь-справочник терминов нормативно-технической документации

Ж. отвлеч. сущ. по прил. сложный Толковый словарь Ефремовой. Т. Ф. Ефремова. 2000 … Современный толковый словарь русского языка Ефремовой

Сложность, сложности, сложности, сложностей, сложности, сложностям, сложность, сложности, сложностью, сложностями, сложности, сложностях (Источник: «Полная акцентуированная парадигма по А. А. Зализняку») … Формы слов

Книги

• Сложность и усложнение как социокультурный феномен. Выпуск № 25 , Ополев П.В.. В работе рассмотрены понятие 171;сложность 187;и социокультурные перспективы усложнения в современном мире, обозначены тенденции изменения человеческой размерности, трансформации в сфере…
• Сложность. Математическое моделирование. Гуманитарный анализ , Н. В. Белотелов, Ю. И. Бродский, Ю. Н. Павловский. В предлагаемой вниманию читателя книге обсуждается одна из центральных проблем использования математического и имитационного моделирования при исследовании социально-экономических систем -…

Наверняка вы не раз сталкивались с обозначениями вроде O(log n) или слышали фразы типа «логарифмическая вычислительная сложность» в адрес каких-либо алгоритмов. И если вы так и не понимаете, что это значит, - эта статья для вас.

Оценка сложности

Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.

Допустим, некоторому алгоритму нужно выполнить 4n 3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n . Тогда говорят, что временная сложность этого алгоритма равна О(n 3) , т. е. зависит от размера входных данных кубически.

Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n) .

Примеры

O(n) - линейная сложность

Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

O(log n) - логарифмическая сложность

Простейший пример - бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива - там его точно нет. Если же меньше, то наоборот - отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

O(n 2) - квадратичная сложность

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n , т. е. n 2 .

Бывают и другие оценки по сложности, но все они основаны на том же принципе.

Также случается, что время работы алгоритма вообще не зависит от размера входных данных. Тогда сложность обозначают как O(1) . Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.

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