Оценка сложности алгоритмов
Для любого программиста важно знать основы теории алгоритмов, так как именно эта наука изучает общие характеристики алгоритмов и формальные модели их представления. Ещё с уроков информатики нас учат составлять блок-схемы, что, в последствии, помогает при написании более сложных задач, чем в школе. Также не секрет, что практически всегда существует несколько способов решения той или иной задачи: одни предполагают затратить много времени, другие ресурсов, а третьи помогают лишь приближённо найти решение.
Всегда следует искать оптимум в соответствии с поставленной задачей, в частности, при разработке алгоритмов решения класса задач.
Важно также оценивать, как будет вести себя алгоритм при начальных значениях разного объёма и количества, какие ресурсы ему потребуются и сколько времени уйдёт на вывод конечного результата.
Этим занимается раздел теории алгоритмов – теория асимптотического анализа алгоритмов.
Предлагаю в этой статье описать основные критерии оценки и привести пример оценки простейшего алгоритма. На Хабрахабре уже есть статья про методы оценки алгоритмов, но она ориентирована, в основном, на учащихся лицеев. Данную публикацию можно считать углублением той статьи.
Определения
Основным показателем сложности алгоритма является время, необходимое для решения задачи и объём требуемой памяти.
Также при анализе сложности для класса задач определяется некоторое число, характеризующее некоторый объём данных – размер входа.
Итак, можем сделать вывод, что сложность алгоритма – функция размера входа.
Сложность алгоритма может быть различной при одном и том же размере входа, но различных входных данных.
Существуют понятия сложности в худшем, среднем или лучшем случае. Обычно, оценивают сложность в худшем случае.
Временная сложность в худшем случае – функция размера входа, равная максимальному количеству операций, выполненных в ходе работы алгоритма при решении задачи данного размера.
Ёмкостная сложность в худшем случае – функция размера входа, равная максимальному количеству ячеек памяти, к которым было обращение при решении задач данного размера.
Порядок роста сложности алгоритмов
Порядок роста сложности (или аксиоматическая сложность) описывает приблизительное поведение функции сложности алгоритма при большом размере входа. Из этого следует, что при оценке временной сложности нет необходимости рассматривать элементарные операции, достаточно рассматривать шаги алгоритма.
Шаг алгоритма – совокупность последовательно-расположенных элементарных операций, время выполнения которых не зависит от размера входа, то есть ограничена сверху некоторой константой.
Виды асимптотических оценок
O – оценка для худшего случая
Рассмотрим сложность f(n) > 0, функцию того же порядка g(n) > 0, размер входа n > 0.
Если f(n) = O(g(n)) и существуют константы c > 0, n0 > 0, то
0 < f(n) < c*g(n),
для n > n0.
Функция g(n) в данном случае асимптотически-точная оценка f(n). Если f(n) – функция сложности алгоритма, то порядок сложности определяется как f(n) – O(g(n)).
Данное выражение определяет класс функций, которые растут не быстрее, чем g(n) с точностью до константного множителя.
Примеры асимптотических функций
| f(n) | g(n) |
|---|---|
| 2n 2 + 7n — 3 | n 2 |
| 98n*ln(n) | n*ln(n) |
| 5n + 2 | n |
| 8 | 1 |
Ω – оценка для лучшего случая
Определение схоже с определением оценки для худшего случая, однако
f(n) = Ω(g(n)), если
0 < c*g(n) < f(n)
Ω(g(n)) определяет класс функций, которые растут не медленнее, чем функция g(n) с точностью до константного множителя.
Θ – оценка для среднего случая
Стоит лишь упомянуть, что в данном случае функция f(n) при n > n0 всюду находится между c1*g(n) и c2*g(n), где c – константный множитель.
Например, при f(n) = n 2 + n; g(n) = n 2 .
Критерии оценки сложности алгоритмов
Равномерный весовой критерий (РВК) предполагает, что каждый шаг алгоритма выполняется за одну единицу времени, а ячейка памяти за одну единицу объёма (с точностью до константы).
Логарифмический весовой критерий (ЛВК) учитывает размер операнда, который обрабатывается той или иной операцией и значения, хранимого в ячейке памяти. 
Временная сложность при ЛВК определяется значением l(Op), где Op – величина операнда.
Ёмкостная сложность при ЛВК определяется значением l(M), где M – величина ячейки памяти.
Пример оценки сложности при вычислении факториала
Необходимо проанализировать сложность алгоритма вычисление факториала. Для этого напишем на псевдокоде языка С данную задачу:
Временная сложность при равномерном весовом критерии
Достаточно просто определить, что размер входа данной задачи – n.
Количество шагов – (n — 1).
Таким образом, временная сложность при РВК равна O(n).
Временная сложность при логарифмическом весовом критерии
В данном пункте следует выделить операции, которые необходимо оценить. Во-первых, это операции сравнения. Во-вторых, операции изменения переменных (сложение, умножение). Операции присваивания не учитываются, так как предполагается, что она происходят мгновенно.
Итак, в данной задаче выделяется три операции:
1) i <= n
2) i = i + 1
На i-м шаге получится log(i).
Таким образом, получается сумма 
.
3) result = result * i
На i-м шаге получится log((i-1)!).
Таким образом, получается сумма 
.
Если сложить все получившиеся значения и отбросить слагаемые, которые заведомо растут медленнее с увеличением n, получим конечное выражение 
.
Ёмкостная сложность при равномерном весовом критерии
Здесь всё просто. Необходимо подсчитать количество переменных. Если в задаче используются массивы, за переменную считается каждая ячейка массива.
Так как количество переменных не зависит от размера входа, сложность будет равна O(1).
Ёмкостная сложность при логарифмическом весовом критерии
В данном случае следует учитывать максимальное значение, которое может находиться в ячейке памяти. Если значение не определено (например, при операнде i > 10), то считается, что существует какое-то предельное значение Vmax.
В данной задаче существует переменная, значение которой не превосходит n (i), и переменная, значение которой не превышает n! (result). Таким образом, оценка равна O(log(n!)).
Оценка эффективности алгоритма
Привет, сегодня поговорим про эффективность алгоритма, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое эффективность алгоритма , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
" Поразительно, скольким программистам приходится слишком дорогим способом выяснять, что их программа не может обработать входные данные раньше, чем через несколько дней машинного времени. Лучше было бы предугадать такие случаи с помощью карандаша и бумаги. "
С. Гудман (S. Goodman), С. Хидетниеми (S. Hedetniemi)
" Лучше меньше, да лучше. "
В.И. Ульянов (Ленин)
эффективность алгоритма — это свойство алгоритма, которое связано с вычислительными ресурсами, используемыми алгоритмом. Алгоритм должен быть проанализирован с целью определения необходимых алгоритму ресурсов. Эффективность алгоритма можно рассматривать как аналог производственной производительности повторяющихся или непрерывных процессов.
Для достижения максимальной эффективности мы желаем уменьшить использование ресурсов. Однако различные ресурсы (такие как время и память) нельзя сравнить напрямую, так что какой из двух алгоритмов считать более эффективным часто зависит от того, какой фактор более важен, например, требование высокой скорости, минимального использования памяти или другой меры эффективности
Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня. Грубо говоря, «приемлемый» здесь означает «алгоритм будет работать умеренное время на доступном компьютере». Поскольку с 1950-х годов наблюдалось значительное увеличение вычислительной мощности и доступной памяти компьютеров, существующий «приемлемый уровень» не был приемлемым даже 10 лет назад.
Выше мы уже говорили о необходимости анализировать конструируемый алгоритм. Такой анализ должен дать четкое представление, во-первых, о емкостной и, во-вторых, о временнОй сложности процесса.
Первая часть вполне ясна: речь идет о размерах памяти, в которой предстоит размещать все данные, участвующие в вычислительном процессе. Естественно, к ним относятся входные наборы, промежуточная и выходная информация. Возможно, не все перечисленные наборы требуют одновременного хранения, — что ж, значит, удается сэкономить. В ряде случаев, впрочем, оценка емкостной сложности становится менее очевидной: так обстоит дело при использовании динамических структур, но об этом — в другой главе.
А вот анализу временнОй трудоемкости мы уделим внимание уже сейчас.
Для оценки эффективности алгоритма( не следует путать с сложностью), обычно используются несколько подходов:
Время выполнения: измеряется время, необходимое для выполнения алгоритма. Этот параметр часто оценивается в больших вычислительных задачах, где требуется обработка больших объемов данных. Время выполнения может быть измерено на реальных данных или на синтетических данных.
Память: измеряется объем памяти, необходимой для выполнения алгоритма. Этот параметр также важен при работе с большими объемами данных, когда память может стать узким местом.
Точность: измеряется насколько хорошо алгоритм решает поставленную задачу. Это может быть оценено по сравнению с другими алгоритмами или по сравнению с известным оптимальным решением.
Масштабируемость: оценка того, насколько алгоритм может быть масштабирован при увеличении размера данных или увеличении количества вычислительных ресурсов.
Устойчивость: оценка того, как алгоритм справляется с шумом или неожиданными изменениями данных.
Сложность: анализируется количество операций, необходимых для выполнения алгоритма. Чем меньше количество операций, тем более эффективен алгоритм.
Кроме того, при оценке эффективности алгоритма важно учитывать его применимость к конкретной задаче и требования пользователя. Например, для некоторых задач более важным параметром может быть точность, в то время как для других — скорость выполнения.
Итак, поставлена некоторая задача, и для ее решения спроектирован алгоритм. Он описывает вычислительный процесс, который завершается за конечное число действий-шагов. Мы уже говорили, что реальное время выполнения каждого отдельного шага зависит от конкретного вычислительного устройства. Иначе говоря, неотъемлемым участником вычислительного процесса, — не алгоритма! — является исполнитель. А вот имея ввиду предполагаемого исполнителя, не грех заранее оценить его вычислительные способности.
Можно сказать, что алгоритм должен быть понятен исполнителю. Это означает, что любое предписание алгоритма должно входить в тот фиксированный набор инструкций, которые исполнитель умеет реализовывать. Скажем, ваш карманный калькулятор рассчитан на выполнение нескольких арифметических операций, а более мощный, программируемый калькулятор, уже готов выполнять несложные программы. Соответственно, наборы встроенных, элементарных, инструкций у этих устройств различаются. Притом, любая команда, которую готов выполнить второй калькулятор, все равно состоит из некоторого числа арифметических и логических операций. Другое дело, что нам не приходится их вызывать по отдельности. Таким образом, либо алгоритм явно предписывает выполнять арифметико-логические операции, — и такой уровень программирования рассчитан непосредственно на работу процессора, — либо используются "укрупненные" инструкции, и для их обработки применяется специальный язык.
Так, общение клиента с банкоматом предусматривает участие двух исполнителей алгоритма — человека и банкомата, причем первый из них обращается ко второму посредством кнопочного интерфейса. Опытный владелец пластиковой карты знаком с процедурой, тем не менее, второй участник процесса не учитывает компетентность клиента, и потому на табло высвечиваются поочередно все необходимые инструкции. Как видим, разработчики системы, обеспечивающей этот диалог, довели пошаговую детализацию алгоритма до определенного уровня "компетентности", разбив укрупненные шаги — "снятия наличности" или "получения справки о счете" — на шаги более мелкие.
Как мы выяснили, исполнитель нашего алгоритма должен "уметь" выполнить любую инструкцию из числа тех, которые он воспринимает как элементарные, а никакие другие он и не выполнит. Собственно, одно из различий между процессорами компьютеров состоит в несовпадении их "личных" наборов инструкций.
Но было бы нелепо в предлагаемом читателю курсе ориентироваться на столь "интеллектуально ограниченного" исполнителя, каким является обыкновенный процессор. Напротив, "способности" нашего подразумеваемого исполнителя должны постепенно развиваться. Потому, по мере удаления от начальных страниц, степень детализации будет уменьшаться, и алгоритмы будут описываться в укрупненных шагах. Так, опытный повар вполне готов исполнить предписание "приготовить ростбиф", — помните, мы с ним выше сталкивались? — как элементарную инструкцию.
Предположим, алгоритм для решения некоторой задачи нам удалось построить. Раз так, что мешает предположить существование и другого алгоритма, и еще следующего? Но если удается сконструировать целый ряд различных алгоритмов решения одной и той же задачи, то кажется разумным — выбрать "наилучший" . Об этом говорит сайт https://intellect.icu . Что под этим следует понимать?
Как правило, речь идет о таком варианте решения, который, в сравнении с конкурентами, нуждается в наименее продолжительном по времени вычислительном процессе. Разумеется, давать такую оценку правомерно, лишь имея ввиду одного и того же потенциального исполнителя.
Далее: скорость реализации выбираемого алгоритма может существенно зависеть от содержания набора входных данных. Скажем, быстрый "в среднем" механизм способен давать сбои в отдельных "плохих" случаях. И, если задача должна наверняка решаться за определенное время работы процессора, то в этом случае, вероятно, мы предпочтем алгоритм более медленный в среднем, зато надежный в худших ситуациях.
За примерами вновь обратимся к некомпьютерной сфере. Чтобы выпить чашку кофе, надо, во всяком случае, подогреть воду. Достаточно удобна и эффективна в этом случае кофеварка или мощный электрочайник. Если к вам в дом, — а это весьма вероятно, — подведено электричество, то способ решения задачи, привлекающий один из указанных приборов, стоит предпочесть в большинстве случаев. Однако неполадки в распределительном электрощите, сколь бы редко они ни возникали, лишат вас ожидаемого удовольствия (как и автора, который ссылается здесь на собственный печальный опыт, когда одновременно с кофеваркой перестает работать и компьютер). Так что газовые плиты пока не стоит отменять.
Впрочем, остается и самый надежный, хотя и наиболее трудоемкий метод: вскипятить воду на открытом огне, разложив небольшой костер. Чтобы читатель не забывал анализировать и емкостную сложность алгоритма, заметим, что последний пример сочетает свойства наихудшей эффективности как по времени, так и по требованиям к ресурсам, учитывая безвозвратный расход горючего и низкий коэффициент полезного действия при изменении агрегатного состояния. Однако даже такой алгоритм имеет право на существование!
Итак, давая оценку быстродействия алгоритма, следует рассмотреть поведение вычислительного процесса в среднем и, отдельно, в экстремальных для него условиях, то есть — в худшем случае.
Моделирование "худших" случаев всегда связано с содержанием самого алгоритма. Можно предложить лишь малое число рецептов выделения и рассмотрения подобных ситуаций. Один из них состоит в проверке поведения алгоритма на входных данных, принимающих граничные значения из разрешенного диапазона. Другой рецепт: тестировать алгоритм на максимально больших по объему входных наборах, что важно для анализа как временнОй, так и емкостной эффективности.
Пожалуй, умение предвидеть "нехорошие" ситуации, — а они нередко возникают при выполнении готовой программы, — как раз и отличает квалифицированного алгоритмиста от обыкновенного кодировщика. В связи с расширением сферы производства программного обеспечения сформировалась даже самостоятельная специализация — "тестеры программ".
Хорошей тренировкой в развитии навыков проектирования контрпримеров к разрабатываемому алгоритму — и, разумеется, программе — станет для читателя выполнение заданий. Построены они по современным, — "олимпиадным", — канонам. Вам будут далее предлагаться многочисленные примеры, решение которых состоит в написании соответствующих программ. Готовые программы предстоит тестировать автоматизированной системе, причем наборы тестов составлены так, чтобы алгоритм прошел через "огонь и воду". Для этого первые тесты проверяют работоспособность "в общем", с точки зрения получения ожидаемого результата, а вот далее, если это соответствует постановке задачи, — "в частности", когда на вход программы подаются "плохие", в рассмотренном нами смысле, наборы.
Однако продолжим обсуждение того, как оценивать временнУю эффективность собственно алгоритма. Обычно ее не связывают с конкретной вычислительной установкой, а оперируют только "шагами". В самом деле, хорошо бы давать такие оценки, которые будут актуальны и "завтра", когда быстродействие техническое, — аппаратное, — наверняка возрастет.
Естественно, любой шаг алгоритма реализуется некоторым числом машинных операций, или тех самых элементарных инструкций исполнителя, поскольку вы вряд ли станете проектировать алгоритм на языке ассемблера. По существу, анализ требует такой степени детализации алгоритма, чтобы в отношении отдельного шага не требовалась его дальнейшая алгоритмическая проработка. Здесь возможны лишь две ситуации: либо фиксированное время исполнения такого шага определено некоторым набором простых, без циклов, команд языка программирования, либо речь идет об "укрупненном" шаге, в отношении которого соответствующий анализ уже проводился и результаты известны.
С точки зрения количества машинных операций, две разных ситуации — обмена содержимым между переменными, занимающими одно машинное слово, или занимающими два машинных слова — неравноценны. Но оценка алгоритмической трудоемкости это не учитывает.
Если воспользоваться известной формулой для суммы арифметической прогрессии, то вычисления также потребуют лишь 3 шага: сложение, умножение и деление. Если же реализовать вычислительный процесс как циклический: цикл с параметром, управляющая переменная "пробежит" значения от 1 до n , — то придется выполнить n шагов алгоритма. Сомнений, какой из алгоритмов более эффективен, кажется, не возникает. Однако вспомните о "худших случаях": при небольших значениях n (скажем, от 2 до 4), "медленный" алгоритм, вероятно, предпочтительнее.
Для алгоритмов, подобных только что рассмотренному, — n шагов для обработки n входных значений, — очевидно, что количество шагов является функцией от числа обрабатываемых элементов. Можно считать, что количество шагов является функцией от количества элементов — f(n) .
В математике существует специальный механизм оценки скорости роста интересующей исследователя величины: ее сравнивают с какой-нибудь функцией, чье поведение хорошо исследовано. При этом используется обозначение g(n)=O(f(n)) , — читается: O-большое), которое мы будем относить к интересующим нас дискретным функциям f(n) натурального n и ко всем функциям g(n) , растущим не быстрее f(n) . Формулировка "растущим не быстрее" означает, что существует такая пара положительных значений M и n0 , что |g(n)|≤M|f(n0)| для n≥n0 . Еще говорят, что функция g(n) — "порядка f(n) для большИх n ".
Нотация Big-O — порядок роста или асимптотическая оценка роста. Big-O = O(n): О — объем данных, n – нотация.
Время сортировки массива зависит от размера сортируемого массива и его упорядоченности. Время работы алгоритма определяется числом шагов, которые он выполняет. Будем считать, что срока псевдокода требует не более чем фиксированного количества элементарных операций, если строка не является формулировкой сложных действий. В последнем случае строка соответствует программной функции, а в основном алгоритме ей соответствует вызов той функции. Вызов функции и ее выполнение отличаются по времени.
Такая O-нотация дает нам верхнюю оценку временнОй трудоемкости алгоритма, его асимптотическую сложность. Обратите внимание, что использование констант M и n0 , фигурирующих в определении, фактически связано с "большими" значениями аргумента n и мало что дает при его малых значениях.
Укажем несколько важных свойств O -операций:
Кроме введенной терминологии, полезна и другая, так называемая o-нотация ("о-малое"). Обозначение o(f(n)) относится к функциям, которые растут быстрее f(n) .
Вновь обращаясь к примеру с суммой арифметической прогрессии, можем сказать, что асимптотическая эффективность алгоритма непосредственного суммирования n элементов соответствует линейной сложности, поскольку его быстродействие, то есть число шагов, согласно свойству (a), есть O(n) .
Вообще говоря, если алгоритм связан с обработкой n входных элементов, и аналитического выражения — формулы — для быстрого вычисления результата в нашем распоряжении нет, то достижение лучшей эффективности, чем O(n) , если это вообще возможно, следует рассматривать как большой успех.
А вот более трудоемкие алгоритмы, при том же объеме входного набора, существуют, и ускорить процесс далеко не всегда удается.
Если предстоит рассмотреть все варианты для выбора наиболее приемлемого в некотором заданном смысле, то трудоемкость алгоритма, очевидно, оценивается как O(n 2 ) , или квадратичная. Согласно свойству (b) O-операций, собственно константа, определяющая трудоемкость каждого отдельного шага оценки "приемлемости", скрыта внутри обозначения, и даже может быть нам неизвестна.
Здесь, очевидно, предстоит проверить n(n-1)(n-2) вариантов, что соответствует кубической трудоемкости — O(n 3 ) .
В наших примерах речь идет о верхних оценках скорости роста трудоемкости. Обычно, при поверхностном анализе алгоритма, такой оценки вполне достаточно, особенно когда речь идет об алгоритмах с трудоемкостью "разного порядка", как то: O(n 2 ) и O(n 3 ) . В общем случае, если эффективность алгоритма определяется вычислительной сложностью обработки многочлена порядка k , часто удовлетворяются оценкой O(n k ) , не обращая внимания, согласно свойству (b), на старший коэффициент.
Такой подход, как правило, оправдывает себя для "большИх" n . Действительно, как следует из определения O-асимптотики, — и это демонстрируют приводимые графики, — сколь бы ни был мал коэффициент при старшем k -члене и, напротив, велик — при любом другом m -члене (m, вклад первого из них в поведение всего многочлена рано или поздно становится решающим.
Однако нередко представляет интерес более тщательный анализ. В частности, когда сравнивают эффективность двух равноценных, с точки зрения O-асимптотики, алгоритмов. Тогда возникает необходимость в уточнении первого "приближения".
Так, оценка O(n 3 ) в последнем примере получена нами без раскрытия скобок в произведении. Для ее уточнения достаточно проделать несколько умножений:
На практике оказывается недостаточно "O(n k )-шкалы" для сравнения временнОй сложности алгоритмов. Так, более эффективным, чем алгоритм с линейной трудоемкостью, является его конкурент, чье поведение оценивается как O(log2n) . Еще быстрее работает алгоритм с постоянной трудоемкостью — O(1) , с одним из них мы уже имели дело — это алгоритм обмена. Соответственно, "между" O(n) и O(n 2 ) находится место для O(n·log2n) . Знакомство с такими алгоритмами нам предстоит.
Классификация алгоритмов по трудоемкости.
О (1)
Большинство инструкций программы запускается один или несколько раз, независимо от n. Т.е. время выполнения программы постоянно. (помещение в стек)
О (n)
Время выполнения программы линейно зависит от n. Каждый входной элемент подвергается небольшой обработке. (поиск min/max в массиве, значения в связанном списке) (for…; i<n ;. )
О (n 2 )
Время выполнения программы является квадратичным. Такие алгоритмы можно использовать для относительно небольших n. Такое время характерно, когда обрабатываются все пары элементов (в цикле двойного уровня вложенности). (сортировки выбором, вставками)
О (n 3 )
Алгоритм обрабатывает тройки элементов (возможно, в цикле тройного уровня вложенности) и имеет кубическое время выполнения. Такой алгоритм практически применим только для малых задач. (умножение матриц)
О (logn)
Программа работает медленнее с ростом n. Такое время характерно для программ, которые сводят большую задачу к набору меньших подзадач, уменьшая на каждом шаге размер подзадачи на некоторый постоянный коэффициент. Общее решение находится в одной из подзадач. Логарифмическая зависимость. (бинарный поиск)
О (n*logn)
Время выполнения программы пропорционально n*log n возникает тогда, когда алгоритм решает задачу, разбивая ее на меньшие подзадачи, решая их независимо и затем объединяя решения подзадач (комбинация). Линерифмическая зависимост
(сортировки быстрая, слиянием)
О (2 n )
Лишь несколько алгоритмов с экспоненциальным временем имеет практическое применение, хотя такие алгоритмы возникают естественным образом при попытке прямого решения задач. (перебор и сравнение различных решений) Для комбинаторных задач нереализуемы. Сведение к приближенному алгоритму с приближенным значением.
Обычно время выполнения в результате анализа выглядит как многочлен, где главным членом является один из вышеприведенных. Коэффициент при главном члене зависит от количества инструкций во внутреннем цикле. Поэтому так важно максимально упрощать количество инструкций во внутреннем цикле. При росте N начинает доминировать главный член, поэтому остальными слагаемыми в многочлене можно пренебречь.
Примеры эффективных алгоритмов
- Быстрая сортировка, первый известный алгоритм сортировки со скоростью порядка
- Пирамидальная сортировка, другой быстрый алгоритм сортировки
- Двоичный поиск для поиска в сортированной таблице
- Алгоритм Бойера — Мура для поиска строки внутри другой строки
Вау!! 😲 Ты еще не читал? Это зря!
- сложность алгоритмов , оценка сложности алгоритмов , анализ сложности алгоритмов , большое o ,
- алгоритм , понятие алгоритма ,
- теория алгоритмов , алгоритм , классы сложности , класс сложности ,
- алгоритмы сортировки , сортировка , сортировка пузырьком , bubble sort ,
Напиши свое отношение про эффективность алгоритма. Это меня вдохновит писать для тебя всё больше и больше интересного. Спасибо Надеюсь, что теперь ты понял что такое эффективность алгоритма и для чего все это нужно, а если не понял, или есть замечания, то нестесняся пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Емкостная сложность алгоритмов
Объясните пожалуйста, на простом примере, как вычислять емкостную сложность алгоритмов.
Буду благодарен, спасибо.
Сложность алгоритмов
Оценить временную сложность алгоритма выбора лучшего хода в русских шашках.
Временная сложность алгоритмов
Сколько времени займет подсчет до 1 миллиарда (не учитывая переполнение)? Определите время работы.
Временная сложность алгоритмов
Здравствуйте! Собственно, задание: даны 2 алгоритма, надо узнать что они выполняют и их временную.
Сложность алгоритмов + паралельные вычисления
Здравствуйте. Возник вопрос касательно сложности алгоритмов. Допустим у нас есть алгоритм.
емкостная сложность — это функция, выражающая зависимость требуемой памяти от размера входных данных.
например, вам дан массив и требуется вывести его в отсортированном порядке. если вам дадут сто чисел, то вам понадобится массив из 100 ячеек. если миллион чисел — массив из миллиона ячеек. зависимость необходимой памяти от размера входных данных линейная. поэтому скажем, что емкостная сложность алгоритма, решающего задачу сортировки .
другая задача. надо найти наибольшую общую подстроку двух строк. предположим, вы умеете решать ее только динамикой и ко всему прочему вы еще и не умеете оптимизировать по памяти эту динамику тогда вы будете насчитывать матрицу dp[длина первой строки][длина второй строки]. ну тогда, если обе строки длиной 10, то вам потребуется матрица из 100 ячеек. а если длины 100, то матрица из 10000 ячеек. зависимость уже квадратичная. тогда сложность оценим как .
КАК ПОСЧИТАТЬ ЁМКОСТНУЮ СЛОЖНОСТЬ?
Подскажите, пожалуйста, что такое емкостная сложность и как её расчитать в Си. Как я понял, это размер памяти, занимаемый программой, но ведь это не просто сумма размеров переменных.
Спасибо!
Если надо, могу программу выложить.
14 ответов
Originally posted by OOMPH
Подскажите, пожалуйста, что такое емкостная сложность и как её расчитать в Си. Как я понял, это размер памяти, занимаемый программой, но ведь это не просто сумма размеров переменных.
Спасибо!
Если надо, могу программу выложить.
Ну во-первых.Я не знаю какую именно ёмкостную сложность тебе сказали вычислить, бывают разные типы, зависящие от выбора едениц, а также критериев подсчёта. Самый простой вариант выглядит так : пусть переменная (числовая) занимает C байт (можно взять,конечно, конкретные велечины для int float итд, ведь они известны) , тогда максимальная ёмкостная сложность программы будет равна числу байт(едениц), которое занимают все переменные (n*C), а также + некоторому числу Z = max < exp1,exp2,exp3>; где exp 1. n — это выражения. Пример:
y = 2 + 1; // занимает такое выражение 2 у.е. памяти (допускаем, что число едениц памяти равно числу переменных). Ну, вот считаешь для всех выражений, находишь этот максимум, прибавляешь к памяти переменных. Затем если у тебя есть структуры — там аналогично. Если есть функции — тоже аналогично, плюс ещё память для каждого аргумента функции. Самый грубый подсчёт выглядит именно так, а вообще -то каждый препод по-своему любит, проверено 🙂