На ранних этапах развития компьютеров при ограниченных объёмах компьютерной памяти (как внешней, так и внутренней) анализ памяти носил принципиальный характер. Все алгоритмы разделяются на такие, которым достаточно ограниченной памяти, и те, которым нужно дополнительное пространство.
Предположим, например, что мы записываем вещественное число из интервала от -10 до +10, имеющее один десятичный знак после запятой. При записи этого числа в вещественно виде большинство компьютеров потратит от 4 до 8 байтов памяти, однако если предварительно умножить число на 10, то мы получим целое число из интервала от -100 до +100, а для его хранения выделяется всего один байт. По сравнению с первым вариантом экономия составляет от 3 до 7 байтов. Программа, в которой сохраняется 1000 таких чисел, экономит от 3000 до 7000 байтов. Если принять во внимание, что еще недавно - в начале 80-х годов прошлого века - у компьютеров была память объёмом лишь 65 536 байтов, экономия получается существенной. Именно эта необходимость экономить память наряду с долголетием компьютерных программ привела к проблеме 2000-го года. Если программа использует много дат, то половину места для записи года можно сэкономить, сохраняя значение 99 вместо 1999. Авторы программ не предполагали в 80-х годах, что их продукция доживёт до 2000-го года.
Некоторую новую ноту внесло распространение миниатюрных электронных устройств например карманных компьютеров и мобильных телефонов. У типичного такого устройства ограничено пространство как для хранения данных, так и для программного обеспечения. И поэтому разработка маленьких программ, обеспечивающих компактное хранение данных вновь становится актуальной.
Два алгоритма выбора наибольшей из четырех величин
Рассмотрим, например, два алгоритма, в которых выбирается наибольшее из четырех величин:
По временным затратам эти алгоритмы одинаковы (в каждом делается 3 сравнения), но первый требует больше памяти из-за временной переменной и именем largest. Это дополнительное место не играет роли, если сравниваются числа или символы, но при работе с другими типами данных оно может стать существенным. Многие современные языки программирования позволяют определить операторы сравнения для больших и сложных объектов или записей. В этих случаях размещение временной переменной может потребовать много места. При анализе эффективности алгоритмов в первую очередь интересен вопрос времени, кроме тех случаев, когда память играет существенную роль.
Комментарии
Отправить комментарий