Опасность, связанная со сложностью алгоритмов

Опасность, связанная со сложностью алгоритмов

Очевидно, что будет разумным избегать алгоритмов, которые масштабируются, как О(n!) или O(2?). Более того, замена алгоритма, который масштабируется, как O(n), алгоритмом, который масштабируется, как O(1), — это обычно серьезное улучшение. Тем не менее это не всегда так, и нельзя принимать решение вслепую, базируясь только на описании "большого-О". Вспомните, что в определении множества О(g(x)) фигурирует константа, на которую умножается значение функции g(x). Поэтому есть возможность, что алгоритм, который масштабируется, как O(1), будет выполняться в течение 3 часов. Следовательно, он будет выполняться всегда в течение 3 часов, независимо от количества входных данных, но это может оказаться дольше, по сравнению с алгоритмом, который масштабируется, как O(n), при небольшом количестве входных данных. При сравнении алгоритмов необходимо всегда принимать во внимание количество входных данных. Не стоит слепо оптимизировать для некоторого случайно выбранного варианта.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

12.3.3 Примеры алгоритмов

Из книги Архитектура операционной системы UNIX автора Бах Морис Дж

12.3.3 Примеры алгоритмов В данном разделе мы рассмотрим четыре алгоритма ядра, реализованных с использованием семафоров. Алгоритм выделения буфера иллюстрирует сложную схему блокирования, на примере алгоритма wait показана синхронизация выполнения процессов, схема


13.1.2. Компромиссы между сложностью интерфейса и реализации

Из книги Искусство программирования для Unix автора Реймонд Эрик Стивен

13.1.2. Компромиссы между сложностью интерфейса и реализации Одно из наиболее ярких замечаний о Unix-традиции, сделанных когда-либо сторонним наблюдателем, содержится в статье Ричарда Гэбриэла (Richard Gabriel), которая называется "Lisp: Good News, Bad News, and How to Win Big" [25]. Гэбриэл в течение


13.1.2. Компромиссы между сложностью интерфейса и реализации

Из книги Искусство программирования для Unix автора Реймонд Эрик Стивен

13.1.2. Компромиссы между сложностью интерфейса и реализации Одно из наиболее ярких замечаний о Unix-традиции, сделанных когда-либо сторонним наблюдателем, содержится в статье Ричарда Гэбриэла (Richard Gabriel), которая называется "Lisp: Good News, Bad News, and How to Win Big" [25]. Гэбриэл в течение


Опасность излишней спецификации

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

Опасность излишней спецификации Почему так плохо использовать конкретное представление в качестве спецификации?Можно напомнить результаты изучения Линцем (Lientz) и Свенсоном (Swanson) стоимости сопровождения. Было установлено, что более 17% стоимости ПО приходится на


5.7. РЕФАКТОРИНГ АЛГОРИТМОВ И ЭВРОРИТМОВ

Из книги Технологии программирования автора Камаев В А

5.7. РЕФАКТОРИНГ АЛГОРИТМОВ И ЭВРОРИТМОВ Алгоритм Нелдера — Мида является широко известным и применяется в качестве алгоритма прямого поиска локального экстремума вещественных функций от 2 до 6 вещественных переменных.Следующий абзац содержит фрагмент текста из книги Д.


Анализ алгоритмов

Из книги Фундаментальные алгоритмы и структуры данных в Delphi автора Бакнелл Джулиан М.

Анализ алгоритмов Рассмотрим два возможных варианта поиска в массиве элемента "John Smith": последовательный поиск и бинарный поиск. Мы напишем код для обоих вариантов, а затем определим производительность каждого из них. Реализация простого алгоритма последовательного


Глава 8 Цифровое общество. Потенциальная опасность

Из книги Знакомьтесь, информационные технологии автора Воловник Аркадий Авральевич

Глава 8 Цифровое общество. Потенциальная опасность Сегодня можно с уверенностью утверждать, что информационные технологии определяют жизнь всего человечества и каждого человека в отдельности. Именно информационные технологии непосредственно влияют на развитие всех


Стандарты алгоритмов шифрования

Из книги Защита от хакеров корпоративных сетей автора Автор неизвестен

Стандарты алгоритмов шифрования Почему так много алгоритмов шифрования? Почему не стандартизируют один из них? Учитывая большое количество алгоритмов шифрования, следует признать, что на этот вопрос нельзя дать простой ответ. Максимум, что возможно, – это достичь


Неверное использование алгоритмов шифрования

Из книги C++ для начинающих автора Липпман Стенли

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


Опасность непредвиденных входных данных

Из книги Новый ум короля [О компьютерах, мышлении и законах физики] автора Пенроуз Роджер

Опасность непредвиденных входных данных Для взаимодействия с пользователем приложение должно обрабатывать входные данные. Входные данные могут быть представлены в простой форме, например щелчком мышки в заданной позиции монитора, или одним введенным символом, или в


Приложение В Сложность алгоритмов

Из книги автора

Приложение В Сложность алгоритмов В компьютерных и связанных с ними дисциплинах полезно выражать сложность, или масштабируемость, алгоритмов с помощью количественных значащих характеристик (в отличие от менее наглядных характеристик, таких как быстрый или медленный).