Что означает эффективность алгоритма программы по памяти

Обновлено: 07.07.2024

Крабоеду поручили срочно написать программу, которая в заданной последовательности неотрицательных чисел находит количество пар, произведение которых кратно 5, а номера различаются не менее, чем на 5. Известно, что значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000. Напишите такую программу и спасите Крабоеда от приближающегося дедлайна.

Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов. Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе.

А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования. Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности \(N\) , т.е. при увеличении \(N\) в \(k\) раз время работы программы должно увеличиваться не более чем в \(k\) раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа \(N\) и не превышает 1 килобайта. Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.

Максимальная оценка за правильную программу, эффективную по времени и по памяти — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

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

Приведем одно из возможных решений задания А на языке С++:

Для эффективного решения задания Б создаем буфер, в котором будем хранить первые пять элементов последовательности, а также создадим счетчики: общий и для элементов, кратных 5. Введем с клавиатуры первые 5 элементов в буфер. Затем каждый новый элемент последовательности будем проверять на кратность 5: если новый элемент кратен 5, то к общему счетчику нужно прибавить количество элементов до него, не считая пяти последних (включая считанное); если новый элемент не кратен 5, то к общему счетчику прибаляем счетчик чисел, кратных 5.

Приведем пример программы на языке С++:

Ответ: _См. решение_

Крабоеду поручили срочно написать программу, которая в заданной последовательности неотрицательных чисел находит количество пар, произведение которых кратно 3, а номера различаются не менее, чем на 7. Известно, что значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000. Напишите такую программу и спасите Крабоеда от приближающегося дедлайна.

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

Приведем одно из возможных решений задания А на языке С++:

Для эффективного решения задания Б создаем буфер, в котором будем хранить первые семь элементов последовательности, а также создадим счетчики: общий и для элементов, кратных 3. Введем с клавиатуры первые 7 элементов в буфер. Затем каждый новый элемент последовательности будем проверять на кратность 3: если новый элемент кратен 3, то к общему счетчику нужно прибавить количество элементов до него, не считая семи последних (включая считанное); если новый элемент не кратен 3, то к общему счетчику прибаляем счетчик чисел, кратных 3.

Приведем пример программы на языке С++:

Ответ: _См. решение_

Крабоеду поручили срочно написать программу, которая в заданной последовательности неотрицательных чисел находит максимальное произведение двух ее элементов, номера которых различаются не менее, чем на 5. Известно, что значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000. Напишите такую программу и спасите Крабоеда от приближающегося дедлайна.

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

Пример входных данных:

Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 2600.

С понятием эффективности связано понятие сложности. Они взаимообратны. Чем более эффективен алгоритм, тем он менее сложен и наоборот. Будем употреблять их как синонимы.

Эффективность алгоритма определяется несколькими компонентами.

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

Описательная эффективность является характеристикой способа, которым задается алгоритм, его описания, программы (объем программы, длина записи, число команд и т.д.)

Вычислительная эффективность характеризует сложность переработки алгоритмом А каждого значения исходных данных, к которым он применим (время работы, емкость памяти и т.д.)

Мы, анализируя алгоритм с точки зрения вычислительной эффективности будем говорить о двух ее составляющих: памяти (или пространство) и времени.

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

Компьютеры обладают ограниченным объемом памяти. Если две программы реализуют идентичные функции, то та, которая использует меньший объем памяти, характеризуется большей пространственной эффективностью. Иногда память становится доминирующим фактором в оценке эффективности программ. Однако в последние годы в связи с быстрым ее удешевлением эта составляющая эффективности постепенно теряет свое значение.

Временная эффективность алгоритма определяется временем, необходимым для ее выполнения.

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

Алгоритм быстрой сортировки характеризуется также и большей интеллектуальной сложностью по сравнению с алгоритмом сортировки вставками. Если предложить сотне людей отсортировать последовательность объектов, то вероятнее всего, большинство из них используют алгоритм сортировки выборками. Маловероятно также, что кто-то из них воспользуется быстрой сортировкой. Причины большей интеллектуальной и пространственной сложности быстрой сортировки очевидны: алгоритм рекурсивный, его достаточно трудно описать, алгоритм длиннее (имеется в виду текст программы), чем более простые алгоритмы сортировки.

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

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

Все алгоритмы разделяются на такие, которым достаточно ограниченной памяти, и те, которым нужно дополнительное пространство [Макконнелл]. Иногда программистам приходится выбирать более медленный алгоритм лишь потому, что он обходится имеющейся памятью и не требует внешних устройств.

Спрос на компьютерную память велик, поэтому и важен вопрос, какие данные необходимо хранить, а также эффективные способы хранения. Проиллюстрируем сказанное на примере. Предположим, что производится запись вещественного числа из сегмента [-10,10], имеющего один десятичный знак после запятой. При записи вещественного числа большинство компьютеров потратит от 4 до 8 байтов памяти. Однако если предварительно умножить число на 10, то для хранения полученного целого числа из сегмента [-100,100] потребуется всего 1 байт.

При взгляде на программное обеспечение, предлагаекмое на рынке сегодня, ясно, что необходимый подробный анализ памяти во многих случаях проведен не был. Объем памяти, необходимый даже для сравнительно простых программ, измеряется мегабайтами. Разработчики программ часто не отдают себе отчет в необходимости экономии места, полагая, что если у пользователя недостаточно памяти, то он может ее приобрести и установить дополнительно. Этот подход является крайне неправильным и негативным, в результате его компьютеры приходят «в негодность» задолго до того, как они действительно устаревают.

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

Вопросы

1. Какие основные характеристики алгоритма оцениваются при его анализе?

2. Как целесообразно оценивать «время» выполнения алгоритма? Почему? Что такое вычислительная сложность алгоритма?

3. В каких случаях сравнивается эффективность работы разных алгоритмов?

4. Должен ли анализ алгоритма учитывать особенности компьютера, на котором этот алгоритм реализован? Почему?

5. Влияют ли входные данные задачи на последовательность действий алгоритма? Привести пример.

6. Что представляют из себя классы входных данных?

7. Насколько значимым в настоящее время является вопрос используемой алгоритмом памяти?

1. Дж. Макконнелл. Основы современных алгоритмов. 2-е дополненное издание. – М.: Техносфера, 2004. – 368 с.

2. Гуц А.К. Математическая логика и теория алгоритмов: Учебное пособие. – Омск: Изд-во Наследие. Диалог-Сибирь, 2003. – 108 с.

3. Деммель Дж. Вычислительная линейная алгебра / Дж.Деммель; пер.с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 430 с.

4. Бахвалов Н.С. Численные методы / Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков. — М.: БИНОМ. Лаборатория знаний, 2006. — 636 с.

5. Каханер Д. Численные методы и программное обеспечение / Д.Каханер, К.Моулер, С.Нэш; пер. с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 575 с.

Лекция 4. Оценка вычислительной сложности алгоритма

План

Предварительные шаги для оценки вычислительной сложности алгоритма

Скорость роста алгоритма

Анализ подходов, связанных с поиском информации

Предварительные шаги для оценки вычислительной сложности алгоритма

Подсчет вычислительной сложности алгоритма состоит из двух основных шагов:

Шаг 1. Выбор значимой операции или группы операций.

Шаг 2. Определение, какие из выбранных операций содержатся в теле алгоритма, а какие составляют накладные расходы или уходят на регистрацию и учет данных.

В качестве значимых часто (но не обязательно) выступают операции двух типов:

Арифметические операции разбиваются на две группы:

Аддитивные операторы (сложения) включают сложение, вычитание, увеличение и уменьшение счетчика.

Мультипликативные операторы (умножения) включают умножение, деление, взятие остатка по модулю.

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

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

Скорость роста алгоритма

Точное значение количества операций, выполненных алгоритмом, не играет существенной роли в его анализе. Более важной оказывается скорость роста этого числа при возрастании объема входных данных. Она называется скоростью роста алгоритма. Именно эта характеристика часто и фигурирует как оценка вычислительной сложности алгоритма.

Существенным является общий характер поведения алгоритмов, а не подробности этого поведения. Предположим, что количество операций четырех различных алгоритмов определяется в соответствии с функциями

где – длина массива входных данных.

Если рассмотреть графики этих функций (рис.4.1)

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

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

Некоторые часто встречающиеся функции приведены в таблице 4.1. Очевидно, что при небольших размерах входных данных значения функций отличаются незначительно, при росте этих размеров разница существенно возрастает. Поэтому существенным является поведение функции на больших объемах входных данных, поскольку на малых объемах принципиальная разница оказывается скрытой.

0.0 1.0 2.3 3.3 3.9 4.3 4.9 5.3 5.6 5.9 6.1 6.3 6.5 6.6

Для иллюстрации последующего вывода рассмотрим пример функции, которая трактуется как закон зависимости количества арифметических операций некоторого гипотетического алгоритма от размера входных данных :

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

Определение. Говорят, что функции и связаны соотношением (или сравнимы)

(читается: функция есть О-большое от ), если

Рассмотрим другой пример:

Ясно, что скорость возрастания будет определяться первым слагаемым - , остальными слагаемыми при оценке скорости роста можно пренебречь. Кроме того:

Из чего вытекает, что

Отбрасывая все младшие члены, скорость роста которых меньше, получаем порядок вычислительной сложности алгоритма [Макконнелл]. В предыдущем рассмотренном примере поскольку , то соответствующий гипотетический алгоритм имеет вычислительную сложность порядка .

Перевод статьи «Algorithm’s Efficiency | Big O “In Simple English”».

Начнем с забавной истории.

Родом я из Демократической Республики Конго в Центральной Африке. У нас там очень низкая скорость интернет-связи. Например, при открытии Gmail загрузка может занимать от 3 до 5 минут (порой процесс прерывается по time out).

В 2009 году подобная проблема со скоростью интернета была у одной компании в Южной Африке. У этой компании было два офиса в 50 милях друг от друга. Сотрудники решили провести занимательный эксперимент и посмотреть, не будет ли быстрее пересылать данные при помощи голубиной почты.

Они поместили 4GB данных на флешку, прикрепили ее к голубю и выпустили его из офиса, чтобы он полетел в другой офис. И…

Почтовый голубь оказался быстрее интернет-связи. Он победил с большим отрывом (иначе история не была бы такой забавной). Больше того, когда голубь долетел до второго офиса, а случилось это через два часа, через интернет загрузилось только 4% данных.

Сложность. Анализ времени работы. Нотация большого «О»

В программировании нотация большого «О» (О-нотация) используется в качестве меры измерения, помогающей программистам оценивать или предполагать эффективность написанного блока кода, скрипта или алгоритма. «Сколько времени потребуется на работу этого кода? Какова его сложность в привязке к тем данным, которые он обрабатывает?»

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

Временная и пространственная сложность

Когда вы пишете код — любой код, на любом языке программирования — вы имеете дело с двумя видами сложности: временной и пространственной.

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

Постоянное время: O(1)

Обратите внимание, что в истории с голубем, рассказанной выше, голубь доставил бы и 5KB, и 10MB, и 2TB данных, хранящихся на флешке, за совершенно одинаковое количество времени. Время, необходимое голубю для переноса данных из одного офиса в другой, это просто время, необходимое, чтобы пролететь 50 миль.

Если использовать О-нотацию, время, за которое голубь может доставить данные из офиса А в офис Б, называется постоянным временем и записывается как O(1). Оно не зависит от объема входящих данных.

Вот пример кода JavaScript с временной сложностью O(1):

Линейное время: O(n)

В отличие от пересылки голубем, передача данных через интернет будет занимать все больше и больше времени по мере увеличения объема передаваемых данных.

Если использовать О-нотацию, мы можем сказать, что время, нужное для передачи данных из офиса А в офис Б через интернет, возрастает линейно и прямо пропорционально количеству передаваемых данных. Это время записывается как O(n), где n — количество данных, которое нужно передать.

Следует учитывать, что в программировании «О» большое описывает наихудший сценарий. Допустим, у нас есть массив чисел, где мы должны найти какое-то определенное число при помощи цикла for. Оно может быть найдено при любой итерации, и чем раньше, тем быстрее функция завершит работу. О-нотация всегда указывает на верхнюю границу, т. е., описывает случай, когда алгоритму придется осуществить максимальное количество итераций, чтобы найти искомое число. Как, например, в том случае, если это число окажется последним в перебираемом массиве.

Вот пример кода на JavaScript с временной сложностью O(n):

Квадратичное время: O(n2)

Квадратичное время представляет алгоритм, производительность которого прямо пропорциональна квадрату размера входящих данных.

Распространенный пример такого алгоритма — два вложенных цикла. По мере увеличения вложенности растет и временная сложность (O(n³), O(n⁴) и т. д.).

Экспоненциальное время: O(2^n)

Если сложность алгоритма описывается формулой O(2^n), значит, время его работы удваивается с каждым дополнением к набору данных. Кривая роста функции O(2^n) экспоненциальная: сначала она очень пологая, а затем стремительно поднимается вверх. Примером алгоритма с экспоненциальной сложностью может послужить рекурсивный расчет чисел Фибоначчи:

Логарифмическое время: O(log n)

Логарифмическое время поначалу понять сложнее. Поэтому для объяснения я воспользуюсь распространенным примером: концепцией бинарного поиска.

Бинарный поиск это алгоритм поиска в отсортированных массивах. Работает он следующим образом. В отсортированном наборе данных выбирается серединный элемент и сравнивается с искомым значением. Если значение совпадает, поиск завершен.

Если искомое значение больше, чем значение серединного элемента, нижняя половина набора данных (все элементы с меньшими значениями, чем у нашего серединного элемента) отбрасывается и дальнейший поиск ведется тем же способом в верхней половине.

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

Эти шаги повторяются, при каждой итерации отбрасывая половину элементов, пока не будет найдено искомое значение или пока оставшийся набор данных станет невозможно разделить напополам:

Вот обычный порядок возрастания времени:

O(1) — постоянное время
O(log n) — логарифмическое время
O(n) — линейное время
O(n²) — квадратичное время
O(2^n) — экспоненциальное время
O(n!) — факториальное время

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

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

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

Читайте также: