Довжина програми

З використанням розглянутих програмних параметрів можна отримати рівняння для оцінки кількісного співвідношення між довжиною програми N і словником h. Це рівняння на перший погляд може здатися дещо несподіваним. Однак ретельний аналіз доводить його правомірність крім того його правильність підтверджується експериментально.
Рядок N, що утворений символами, що входять до словника з h символів, повинен підкорятися ряду обмежень. Вимога за якою кожен символ словника повинен з'явитися щонайменше хоча б один раз, гарантує виконання умови

,

що визначає нижню границю для N визначену через h.

Знайдемо верхю границю для N. Розібємо рядок довжини N на підрядки довжиною h. Поділена таким чином програма на ЕОМ складається з N/h операторів довжиною h кожен. Тепер якщо ми захочемо, щоб рядок не містив двох однакових підрядків довжини h, то з'явиться шукана верхня межа.

Вимога відсутності дублікатів підрядків довжини h є досить обгрунтованою у програмах для ЕОМ, в яких економія висловів призводить до того, що загальному подвираженій дається окреме ім'я, тому його треба обчислювати тільки один раз. Отже, якщо загальний підвираз довжиною h необхіден програмі більше одного разу, присвоювання його окремому операнду збільшить h (число типів операторів) на одиницю.

Число можливих комбінацій з h елементів взятих по h, добре відоме з курсу матиматики і складає

N £ h^h+1

Якщо врахувати, що оператори і операнди, як правило чергуються, то можна отримати інше співвідношення

N£h´h₁^h1´h₂^h2

Верхня межа для цієї нерівності повинна включати не тільки впорядковану множину з N елементів, що представляють досліджувану програму, але і її будь-які підмножини. Сімейство всіляких підмножин з N елементів містить 2^N елементів. Отже, ми можемо прирівняти число можливих комбінацій з операторів і операндів (рівне числу підрядків N / h) числу підмножин з N елементів і виразити довжину реалізації алгоритму через його словник. З рівняння

2^N = h₁^h1´h₂^h2

отримуємо

N = log₂ (h₁^h1´h₂^h2)

або N = log₂ h₁^h1 + log₂ h₂^h2

Це дає нам рівняння оцінки довжини

h₁ log₂h₁ + h₂ log₂h₂ (1.1)

У цьому виразі символ N забезпечили Ù для того, щоб відрізняти обчислену (теоретичну) оцінку довжини від значення N отриманого в результаті безпосереднього вимірювання (досліджуваної довжини). Ця оцінка відповідає основним концепціям теорії інформації, за якими частота використання операторів і операндів у програмі пропорційна двійковому логарифму кількості їх типів. Вираз (1.1) являє собою ідеалізовану апроксимацію виміряної довжини , справедливу для програм що не містять недосконалостей (стилістичних помилок). Експериментальні дослідження ряду авторів на представницькій групі програм показали, що для стилістично коректних програм відхилення в оцінці їхньої теоретичної довжини від дослідженої не перевищують (10-15)%.