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

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

Вот три вопроса, которые чаще всего возникают при попытке количественно оценить сложность предмета исследования (дома, бактерии, проблемы, процесса, инвестиционной схемы): 

1. Насколько сложно его описать? 

2. Насколько сложно его создавать? 

3. Какой у него уровень организации? 

Используя эти вопросы, я разделил метрики сложности на группы. Метрики внутри группы зачастую оказываются родственными величинами. 

Сложность описания 

Обычно сложность системы напрямую связана со степенью сложности описания системы во всей ее полноте. Яркими примерами данной группы метрик (обычно измеряемых в битах) являются следующие:

• Информация (Information);

• Энтропия (Entropy); 

• Алгоритмическая сложность или алгоритмическое информационное наполнение (Algorithmic complexity or algorithmic information content);  

• Минимальный размер описания (Minimum description length);

• Информация по Фишеру (Fisher information);

• Энтропия Реньи (Renyi entropy);

• Размер кода (отсутствие префиксов, Хаффман, Шеннон-Фано, с исправлением ошибок, Хэмминг) / Code length (prefix-free, Huffman, Shannon-Fano, error-correcting, Hamming); 

• Информация Чернова (Chernoff information); 

• Размерность (Dimension);

• Фрактальная размерность (Fractal dimension); 

• Сложность Лемпеля-Зива (Lempel-Ziv complexity). 

Сложность создания

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

• Вычислительная сложность (Computational complexity);

• Временная вычислительная сложность (Time computational complexity); 

• Пространственная вычислительная сложность (Space computational complexity);  

• Информационная сложность (Information-based complexity); 

• Логическая глубина (Logical depth); 

• Термодинамическая глубина (Thermodynamic depth);

• Стоимость (Cost); 

• Закодированность (Crypticity).

Сложность организации

Сложность также часто связана с организационными аспектами. Метрики данной группы можно дополнительно разделить на два подкласса. 

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

• Эффективная сложность (Effective complexity);  

• Метрическая энтропия (Metric entropy); 

• Фрактальная размерность (Fractal dimension); 

• Избыточная энтропия (Excess entropy); 

• Стохастическая сложность (Stochastic complexity); 

• Степень детализации (Sophistication); 

• Эффективная сложность измерения (Effective measure complexity); 

• Истинная сложность измерения (True measure complexity);

• Топологической размер машинного эпсилона (Topological epsilon-machine size); 

• Условная информация (Conditional information); 

• Условно-алгоритмическое информационное наполнение (Conditional algorithmic information content);

• Размер схемы (Schema length); 

• Идеальная сложность (Ideal complexity); 

• Иерархическая сложность (Hierarchical complexity);

• Разнообразие подграфов древа (Tree subgraph diversity); 

• Однородная сложность (Homogeneous complexity); 

• Грамматическая сложность (Grammatical complexity). 

б) На основе объема информации, распределенной между частями системы, являющегося результатом организационной структуры:

• Взаимная информация (Mutual information); 

• Алгоритмическая взаимная информация (Algorithmic mutual information);  

• Пропускная способность канала (Channel capacity); 

• Корреляция (Correlation); 

• Хранимая информация (Stored information); 

• Организация (Organization).

Связанные концепции 

В дополнение к перечисленным выше метрикам существует ряд связанных концепция, которые не являются количественными метриками сложности, но тесно взаимосвязаны между собой. К таким концепциям относятся: 

• Дальняя упорядоченность (Long-range order);

• Самоорганизация (Self-organization);

• Сложные адаптивные системы (Complex adaptive systems); 

• Грань хаоса (Edge of chaos). 

Пожалуйста, дополняйте этот список своими примерами, независимо от того, попадают ли они в принятую здесь классификационную схему.

Информация о продукте

Материал подготовлен в рамках курса «Архитектура и шаблоны проектирования». Если вам интересно узнать подробнее о формате обучения и программе, познакомиться с преподавателем курса — приглашаем на день открытых дверей онлайн. Регистрация здесь.