Нотація О-велике і складність соціальних взаємодій

Якщо вам доводилося сидіти на нестерпно нудній нараді, де дві людини обговорюють проблему, а всі інші є глядачами, ви готові прийняти ідею про те, що такий спосіб взаємодії не ефективний. Можливо, ви також задумувалися про альтернативи. Помилка організаторів зустрічі була в тому, що вони вибрали форму взаємодії не відповідне завдання, і, тим самим, прирекли велику кількість людей на втрату часу.

Деякий час тому, я зрозумів, що до оцінки складності соціальних взаємодій, можна застосовувати ті ж підходи, що і до оцінки складності алгоритмів - а значить можна побачити їх плюси, мінуси і області застосування. Нижче короткий список найбільш частих варіантів, з якими я мав справу.

О (ⁿ2): Нарада рівноправних учасників. n осіб обговорюють питання, причому для досягнення взаєморозуміння, кожному учаснику потрібно поспілкуватися з кожним. Всього буде здійснено n * (n-1 )/2 соціальних взаємодій (еквівалентно завданню підрахунку числа рукостискань в групі з n осіб), тобто складність алгоритму О (n2). Здавалося б, за рахунок того, що спілкування одночасно можуть здійснювати n/2 пар людей, оцінка за часом - О (n), проте на реальних нарадах в один момент часу говорить тільки одна людина, тому оцінка для гіршого випадку - О (n2). Якщо час взаємодії - 5 хвилин і для досягнення повного взаєморозуміння в групі потрібно дві ітерації, то нарада трьох осіб триватиме 30 хвилин, чотирьох - годину, п'ятьом потрібно 1 годину 40 хвилин для знаходження спільного рішення (що підозріло схоже на правду). Якщо ж число ітерацій залежить від числа учасників, ми отримуємо ще більш сумні оцінки.

Але не все так погано!

- По-перше, не всі учасники наради можуть бути незалежні і рівноправні, вони можуть утворювати групи інтересів (наприклад, начальник і двоє його підлеглих), тоді обговорення відбувається не між індивідуальними учасниками, а між групами, представником якої завжди є одна людина. Представник може змінюватися в ході обговорення, але він завжди тільки один. У такому випадку складність соціальної взаємодії - О ((n/m⁾ 2), де m - середня кількість учасників кожної групи, присутньої на зустрічі.

- По-друге, О (ⁿ2) - найгірша оцінка. Може виявитися, що кожна сторона висловлює свою позицію по черзі, а кожен наступний будує своє висловлювання з урахуванням всього почутого раніше. Останній учасник пропонує варіант вирішення проблеми - і всі учасники обговорення погоджуються з ним або вносять свої незначні зміни. В такому випадку, для прийняття рішення достатньо всього лише 2n дій. Мораль: підготовлений виступ і модератор, що визначає порядок обговорення, можуть заощадити дуже багато часу.

О (n * log (n)): вироблення командного рішення через делегатів. Найчастіше для прийняття рішення потрібно залучити дійсно багато людей. Рішення може охоплювати технічно складну область або для реалізації можуть знадобитися зусилля великої кількості людей. Після того, як завдання поставлено, кожен з учасників пропонує вирішення своєї частини завдання, викладаючи його делегату (наприклад, керівнику свого відділу). Делегат узагальнює отримані пропозиції і викладає їх делегату другого рівня (обраного серед делегатів першого рівня), який, у свою чергу, підсумовує отримані пропозиції і викладає їх делегату третього рівня - і так далі. Продовживши рекурсивно алгоритм і дійшовши до людини приймаючого фінальне рішення, ми отримаємо варіант, який, в тій чи іншій мірі, буде враховувати думку кожного з учасників. Причому отримаємо ми його досить швидко - за рахунок того, що спілкування з делегатом відмінно паралелиться, ми отримуємо відповідь за O (_m * logm (n)), де m-характерне число людей в групі.

О (n): ланцюжок узгоджень. Найчастіше рішення вже є, потрібно просто пройти стандартизовану процедуру його узгодження. Наприклад - узгодити додавання нового товару на полицю. Тут складність однієї спроби буде рівна n, де n - число інстанцій, які потрібно буде пройти. Так, число спроб ніяк не обмежене, але, тому що вимоги заздалегідь відомі, воно, зазвичай, мало.

О (n): оповіщення. Ідеально підходить для ситуацій, коли потрібно довести якусь інформацію в незмінному вигляді до великої кількості людей. Кожен з групи витратить час на ознайомлення, таким чином трудовитрати складуть n соціальних взаємодій. У поганих випадках спосіб може приймати вигляд «прошу ознайомитися з наказом і прийняти до виконання», в хороших - це просто перевірка на коректність даних, прописана в коді. Відмінності між цими випадками - в числі людей, які реально зіткнуться з оповіщенням (у другому - значно менше), а також в відмінностях у вимогах до пам'яті виконавця (у другому - не потрібно пам'ятати хоч щось до моменту, коли обмеження спрацює). Але, особисто мені подобається в даному підході те, що він О (1) за часом для відправника - трудовитрати залишаться незмінні незалежно від числа людей, які повідомлення отримають. Темна сторона того ж правила - листи з десятками людей у копії.

О (log (n)): оповіщення через делегатів. Використовується коли потрібно сповістити тільки одну людину, але не відомо - кого саме. Приклад - завдання, яке спускається на управління, потім передається керівнику відділу, потім - безпосередньому виконавцю. Альтернативний шлях - створення «єдиного вікна» через яке приймаються всі завдання/розпорядження/побажання. Такий спосіб постановки завдання як і раніше є костянтним за складністю для відправника, але набагато менш трудовитратний для приймаючої сторони, тому саме приймаюча сторона, як правило, є ініціатором зміни способу обміну з «оповіщення» на «оповіщення через делегатів».

О (1): вирішення проблеми через стандартний інтерфейс. Ідеальна ситуація до якої, на мій погляд, треба прагнути. Проблема відома, як і шляхи її вирішення, а значить - можна створити інтерфейс, який допоможе людині вирішити її проблему без будь-яких контактів з іншими людьми, причому швидкість вирішення проблеми ніяк не залежить від кількості людей, які з нею зіткнулися. Можна сказати, що це те ж «оповіщення», але вже з точки зору відправника, а реальні витрати з боку користувачів - все ще О (n). Це так, але я вирішив виділити даний спосіб, оскільки, незважаючи на математичну еквівалентність, він дає новий погляд на проблему.

Чи є способи взаємодії із зовнішнім світом зі складністю гірше, ніж О (ⁿ2)? Безумовно так - за аналогією з болотним сортуванням можна придумати варіанти, які будуть жахливо непрактичним. Вважаю, що вони не зустрічається на практиці тільки тому, що всі реальні завдання вирішуються менш трудовитратними алгоритмами.

Якщо є підходи, при яких проблема вирішується за костянтний час - навіщо тоді потрібні всі інші методи? Вважаю, що основна причина - у свободі прийняття рішень. Разом з поліпшенням асимптотики свобода поступово йде. У нараді рівноправних учасників, діапазон рішень обмежений тільки повноваженням людей, які беруть участь у нараді. Цей інструмент добре підходить для прийняття важливих унікальних рішень. При використанні стандартних інтерфейсів діапазон рішень значно звужується.

Практичні слідства:

- не кличте на наради рівноправних учасників більше 5 осіб. Якщо час однієї взаємодії між людьми - 5 хвилин, швидше за все, ви не вкладіться в 1 годину обговорення.

- не кличте на наради нерівноправних учасників більше 15 осіб (5 начальників + 2 підлеглих з кожного боку) - однієї години вам знову не вистачить

- не кличте на наради людей, від яких потрібен тільки «ок» - пишіть протокол за результатами зустрічі і просите його узгодити

- розпорядження, вказівки, інформаційні повідомлення (і, можливо, наступні голосування) - єдиний ефективний спосіб спілкування, якщо зацікавлених сторін більше декількох десятків

- якщо у відділі більше 10 осіб - створіть «єдине вікно» куди будуть надходити стандартні вимоги/побажання/запити.

- якщо ви або ваші співробітники не встигають виконувати завдання, які до них приходять - подумайте, чи можете ви поліпшити асимптотику змінивши спосіб взаємодії із зовнішнім світом.

P.s. На жаль, швидкість взаємодії між людьми, не подвоюється кожні два роки.

Оптимізуйте своє спілкування і будьте щасливі.