СКЛАДНІСТЬ АЛГОРИТМУ

сім класів зростання: скільки кроків, скільки часу і як далеко пускає кожен

Аркуш зроблено як памʼятку, а не як таблицю: угорі те, заради чого його вішають на стіну й читають з іншого кінця кімнати, нижче — повна довідка дрібнішим.

Три розміри в одному архіві — від аркуша на холодильник до плаката на стіну.

Формати: A4 · A3 · A2
Що ви отримаєте: PDF, готові до друку, по одному на кожен формат, з усіма літерами в кривих — нічого не треба ставити й ніщо не попливе.
Предмет: код · початківцям · довідник · кабінет

Модель, за якою пораховано все на аркуші: крок — одна елементарна дія, машина робить мільярд кроків за секунду, логарифм двійковий і округлений угору, рік — 365,25 доби. Сталі множники відкинуто: саме про них запис O() навмисне мовчить, і саме тому він показує, як росте ціна, а не скільки вона на конкретній машині.

ЗАЛІЗО МНОЖИТЬ, А КЛАС ЗРОСТАННЯ ДОДАЄ

Поставте вдесятеро швидшу машину. У класі O(n) вона справді дасть удесятеро більше: 1 000 000 000 замість 100 000 000. У O(n²) — уже лише втричі: 100 000 замість 31 622, тобто в 3,2 раза.

А в O(2ⁿ) вона додасть 4 елементи — з 29 до 33. У O(n!) — 1 елемент: з 12 до 13. Ось чому кращий алгоритм не має заміни в залізі: залізо множить, а клас зростання додає.

Що на аркуші

Модель, за якою пораховано все на аркуші: крок — одна елементарна дія, машина робить мільярд кроків за секунду, логарифм двійковий і округлений угору, рік — 365,25 доби. Сталі множники відкинуто: саме про них запис O() навмисне мовчить, і саме тому він показує, як росте ціна, а не скільки вона на конкретній машині.
Колір несе зміст, але зміст не тримається лише на кольорі — аркуш читається і в ЧБ.
Жодного пояснення про те, як ми його робили: на аркуші лише те, що потрібно читачеві.

Друк

Три розміри в архіві: A4 — 210×297 мм, A3 — 297×420 мм, A2 — 420×594 мм.
Увесь текст переведено в криві. Шрифти ставити не треба, і ніщо не попливе на чужій машині.
Білий фон і ощадна заливка — аркуш друкується на побутовому принтері без відра фарби.
Поля не менші за 10 мм: побутовий принтер не друкує під обріз.
Жоден штрих не тонший за 0,3 мм, тож нічого не зникне при друці.

Чому цим числам можна вірити. Кожне лічильне число тут обчислене з даних, а не набране руками, і аркуш проходить 9 незалежних перевірок, перш ніж його дозволено зібрати: скільки елементів, у якому порядку і саме твердження у виділеному блоці. Не пройде бодай одна — файла просто не буде.

Схоже

СКЛАДНІСТЬ АЛГОРИТМУ

ЗАЛІЗО МНОЖИТЬ, А КЛАС ЗРОСТАННЯ ДОДАЄ

Що на аркуші

Друк

Схоже

ВІХИ ШТУЧНОГО ІНТЕЛЕКТУ

ТАБЛИЦЯ ASCII

АУДІОФОРМАТИ

КОДУВАННЯ BASE32