Род Стивенс

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

Для любого основания В значение log2B - константа. Это означает, что для оценки по порядку сложности основание логарифма не имеет значения. Другими словами, 0(log2N) равно O(bg10N) или 0(logBN) для любого В. Поскольку основа­ние логарифмов не имеет значения, часто просто пишут, что сложность алгоритма составляет O(logN).

В программировании используется двоичная система счисления, поэтому ло­гарифмы, используемые при анализе сложности алгоритмов, обычно имеют осно­вание 2. Для того чтобы упростить выражения, мы везде будем писать logN, под­разумевая log2N. Если используется другое основание, это будет обозначено особо.

Скорость работы алгоритма в реальных условиях

Несмотря нато, что малые члены и постоянные множители отбрасываются при изучении сложности алгоритмов, часто их необходимо учитывать для фактичес­кого написания программ. Эти числа становятся особенно важными, когда размер задачи мал, а константы большие.

Предположим, нужно рассмотреть два алгоритма, которые выполняют одну и ту же задачу. Первый выполняет ее за время O(N), а второй - за время 0(N2). Для больших N первый алгоритм, вероятно, будет работать быстрее.

При более близком рассмотрении обнаруживается, что первый описывается функцией f(N) = 30 * N + 7000, а второй - f(N) = N2. В этом случае второй алго­ритм при N меньше 100 существенно быстрее. Если вы знаете, что размер данных задачи не превышает 100, то целесообразнее использовать второй алгоритм.

С другой стороны, время выполнения разных инструкций может СИЛЬНО отли­чаться. Если первый алгоритм использует быстрые операции с памятью, а второй - медленное обращение к диску, то первый алгоритм будет эффективнее в любом случае.

Проблему выбора оптимального алгоритма осложняют и другие факторы. На­пример, первый алгоритм может требовать больше памяти, чем установлено на компьютере. Но на реализацию второго алгоритма, если он гораздо сложнее, мо­жет уйти больше времени, а его отладка превратится в настоящий кошмар. Иногда подобные практические соображения могут сделать теоретический анализ слож­ности алгоритма почти бессмысленным.

Тем не менее анализ сложности помогает понять особенности алгоритмов и опре­делить, в каком месте программы производится большая часть вычислений. Усовер­шенствовав код в этих частях, можно существенно увеличить производительность программы в целом.

Иногда лучшим способом для определения наиболее эффективного алгорит- маявляется тестирование. При этом важно, чтобы использовались данные, макси­мально приближенные к реальным условиям. В обратном случае результаты тес­тирования могут сильно отличаться от действительных.

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

Страницы раздела: 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.