Род Стивенс

Книги → Delphi. Готовые алгоритмы → Глава 1. Основные понятия

Таким образом, уравнение сложности, которое содержит несколько этих функ­ций, при приведении в систему оценки сложности по порядку величины будет со­кращаться до функции, расположенной ниже в таблице. Например, 0(log(N) + N2) - это то же самое, что и 0(№).

Сможет ли алгоритм работать быстрее, зависит от того, как вы его используе­те. Если вы запускаете алгоритм раз в год для решения задач с достаточно малыми объемами данных, то вполне приемлема производительность 0(№). Если же алго­ритм выполняется под наблюдением пользователя в интерактивном режиме, опе­рируя большими объемами данных, то может быть недостаточно и производитель­ности O(N).

Обычно алгоритмы со сложностью N * log(N) работают с очень хорошей ско­ростью. Алгоритмы со сложностью Nc при небольших значениях С, например N2, применяются, когда объемы данных ограничены. Вычислительная сложность ал­горитмов, порядок которых определяется функциями CN и N! очень велика, поэто­му эти алгоритмы пригодны только для решения задач с очень малым объемом перерабатываемой информации.

Один из способов рассмотрения относительных размеров этих функций за­ключается в определении времени, которое требуется для решения задач различных размеров. Табл. 1.3 показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы. Из таб­лицы видно, что только небольшие задачи можно решить с помощью алгоритмов со сложностью 0(CN), и самые маленькие - с помощью алгоритмов со сложнос­тью 0(N!). Для решения задач порядка 0(N!), где N = 24, потребовалось бы боль­ше времени, чем существует вселенная.

Логарифмы

Прежде чем продолжить изложение материала, необходимо рассмотреть ло­гарифмы, так как они играют важную роль во многих алгоритмах. Логарифм чис­ла N по основанию В - это степень Р, в которую нужно возвести число В, чтобы выполнялось равенство Вр = N. Например, выражение l°g28 следует читать «сте­пень, в которую необходимо возвести 2, чтобы получилось 8». В этом случае, 23=*= 8 или log28 = 3.

Преобразовывать логарифмы от одного основания к другому можно с помо­щью зависимости logBN - logcN/logcB. Если вы хотите преобразовать lоg28 к осно­ванию 10, то это будет выглядеть так: log10N = log2N/log210. Значение bg210 - кон­станта, которая приблизительно равна 3,32. Поскольку постоянные множители при оценке по порядку сложности можно опустить, допускается не учитывать член log210.

← предыдущая следующая →

Страницы раздела: 1 2 3 4 5 6 7 8 9 10 11

Публикация компанией Dropbox кода Zulip – средства общения для IT-разработчиков

20.11.2015
Одной из одобрительно встреченных программистами инициатив, реализующихся в рамках акции Hack Week, стала публикация исходного кода приложения Zulip – веб-приложения для общения между собой разработчиков в сфере IT-технологий.

Объединение ОС Android и Chrome

17.11.2015
Слухи об объединении двух крупнейших ОС компании Google, Android и Chrome, гуляют по Интернету уже более 5 лет, но до сих пор этого не случилось, хотя очевидно, что с течением времени эти ОС становятся всё более похожими: так, в последнее время появилось немало Android-устройств, к которым прилагаются клавиатуры, а Chrome OS «научилась» работать с сенсорными экранами.

Конференция Linux Piter 2015

15.11.2015
Уже почти через неделю в Санкт-Петербурге впервые в истории пройдёт конференция, посвящённая проблемам свободного программного обеспечения – Linux Piter 2015.