Складність алгоритмів

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

няти особливості цієї поведінки

Алгоритми

Алгоритм – це послідовність дій, можливо, з одним входом або більше і, в кінцевому рахунку, з одним результатом або виходом Наприклад, підрахунок кількості людей в кімнаті являє собою алгоритм, для якого люди, що знаходяться в кімнаті, є вхідними даними, а кількість людей в кімнаті – вихідними даними Операції заміщення сторінок в ядрі Linux або планування виконання процесів – Це теж приклади алгоритмів Математично алгоритм аналогічний функції (або, принаймні, може бути змодельований за допомогою функції) Наприклад, якщо ми позначимо алгоритм підрахунку людей в кімнаті буквою f, а кількість людей, яких необхідно порахувати, буквою х, то функцію підрахунку кількості людей можна записати наступним чином

y = f (х)

У цьому виразі буквою у позначений час підрахунку кількості людей в кімнаті

Джерело: Лав, Роберт Розробка ядра Linux, 2-е видання : Пер з англ – М: ТОВ «ІД Вільямс »2006 – 448 с : Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*