Сделай Сам Свою Работу на 5

Математическое толкование символа O().





Лекция 1.

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

 

 

Эта аналогия, однако, не является полной. Некоторые свойства числовых отношений не выполняются для их функциональных аналогов.

Оценки времени исполнения. Cимвол O()
Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - математически оценить время исполнения подсчетом операций. Рассмотрим алгоритм вычисления значения многочлена степени n в заданной точке x. Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x1 + a0 Алгоритм 1 - для каждого слагаемого, кроме a0 возвести x в заданную степень последовательным умножением и затем домножить на коэффициент. Затем слагаемые сложить. Вычисление i-го слагаемого(i=1..n) требует i умножений. Значит, всего 1 + 2 + 3 + ... + n = n(n+1)/2 умножений. Кроме того, требуется n+1 сложение. Всего n(n+1)/2 + n + 1= n2/2 + 3n/2 + 1 операций. Алгоритм 2 - вынесем x-ы за скобки и перепишем многочлен в виде Pn(x) = a0 + x(a1 + x(a2 + ... ( ai + .. x(an-1 + anx))). Например, P3(x) = a3x3 + a2x2 + a1x1 + a0 = a0 + x(a1 + x(a2 + a3x)) Будем вычислять выражение изнутри. Самая внутренняя скобка требует 1 умножение и 1 сложение. Ее значение используется для следующей скобки... И так, 1 умножение и 1 сложение на каждую скобку, которых.. n-1 штука. И еще после вычисления самой внешней скобки умножить на x и прибавить a0. Всего n умножений + n сложений = 2n операций. Зачастую такая подробная оценка не требуется. Вместо нее приводят лишь асимптотическую скорость возрастания количества операций при увеличении n. Функция f(n) = n2/2 + 3n/2 + 1 возрастает приблизительно как n2/2 (отбрасываем сравнительно медленно растущее слагаемое 3n/2+1). Константный множитель 1/2 также убираем и получаем асимптотическую оценку для алгоритма 1, которая обозначается специальным символом O(n2). Это - верхняя оценка, т.е количество операций(а значит, и время работы) растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите на таблицу, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций.  
n log n n*log n n2
2,048 65,536
4,096 49,152 16,777,216
65,536 1,048,565 4,294,967,296
1,048,576 20,969,520 1,099,301,922,576
16,775,616 402,614,784 281,421,292,179,456

Если считать, что числа в таблице соответствуют микросекундам, то для задачи с n=1048576 элементами алгоритму с временем работы O(log n)потребуется 20 микросекунд, алгоритму со временем O(n) - 17 минут, а алгоритму с временем работы O( n2 ) - более 12 дней... Теперь преимущество алгоритма 2 с оценкой O(n) перед алгоритмом 1 достаточно очевидно.





Наилучшей является оценка O(1)...В этом случае время вообще не зависит от n, т.е постоянно при любом количестве элементов.

Таким образом, O() - "урезанная" оценка времени работы алгоритма, которую зачастую гораздо проще получить, чем точную формулу для количества операций.

Итак, сформулируем два правила формирования оценки O().

При оценке за функцию берется количество операций, возрастающее быстрее всего.
То есть, если в программе одна функция, например, умножение, выполняется O(n) раз, а сложение - O(n2) раз, то общая сложность программы - O(n2), так как в конце концов при увеличении n более быстрые ( в определенное, константное число раз ) сложения станут выполнятся настолько часто, что будут влиять на быстродействие куда больше, нежели медленные, но редкие умножения. Символ O() показывает исключительно асимптотику!



При оценке O() константы не учитываются.
Пусть один алгоритм делает 2500n + 1000 операций, а другой - 2n+1. Оба они имеют оценку O(n), так как их время выполнения растет линейно.

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

Другое следствие опускания константы - алгоритм со временем O(n2) может работать значительно быстрее алгоритма O(n) при малых n... За счет того, что реальное количество операций первого алгоритма может быть n2 + 10n + 6, а второго - 1000000n + 5. Впрочем, второй алгоритм рано или поздно обгонит первый... n2 растет куда быстрее 1000000n.

Основание логарифма внутри символа O() не пишется.
Причина этого весьма проста. Пусть у нас есть O( log2n). Но log2n=log3n/log32, а log32, как и любую константу, асимптотика - символ О() не учитывает. Таким образом, O( log2n) = O( log3n).

К любому основанию мы можем перейти аналогично, а значит и писать его не имеет смысла.

 

Математическое толкование символа O().

Определение
O(g) - множество функций f, для которых существуют такие константы C и N, что |f(x)| <= C|g(x)| для всех x>N.
Запись f = O(g) дословно обозначает, что f принадлежит множеству O(g). При этом обратное выражение O(g) = f не имеет смысла.

В частности, можно сказать, что f(n) = 50n принадлежит O(n2). Здесь мы имеем дело с неточной оценкой. Разумеется, f(n) <= 50n2 при n>1, однако более сильным утверждением было бы f(n) = O(n), так как для C=50 и N=1 верно f(n) <= Cn, n>N.

Другие виды оценок.

Наряду с оценкой O(n) используется оценка Ω(n) [читается как "Омега большое от эн"]. Она обозначает нижнюю оценку роста функции. Например, пусть количество операций алгоритма описывает функция f(n) = Ω(n2). Это значит, что даже в самом удачном случае будет произведено не менее порядка n2действий.
...В то время как оценка f(n) = O(n3) гарантирует, что в самом худшем случае действий будет порядка n3, не больше.

Также используется оценка Θ(n)["Тэта от эн"], которая является гибридом O() и Ω().
Θ(n2) является и верхней и нижней асимптотической оценкой одновременно - всегда будет выполняться порядка n2 операций. Оценка Θ() существует только тогда, когда O() и Ω() совпадают и равна им.

Для рассмотренных выше алгоритмов вычисления многочлена найденные оценки являются одновременно O(), Ω() и Θ().
Если добавить к первому алгоритму проверки на x=0 в возведении в степень, то на самых удачных исходных данных(когда x=0) имеем порядка n проверок, 0 умножений и 1 сложение, что дает новую оценку Ω(n) вкупе со старой O(n2).

Как правило, основное внимание все же обращается на верхнюю оценку O(), поэтому, несмотря на "улучшение", алгоритм 2 остается предпочтительнее.

Итак, O() - асимптотическая оценка алгоритма на худших входных данных, Ω() - на лучших входных данных, Θ() - сокращенная запись одинаковых O() иΩ().


Оценка программ

Для большинства проблем существует много различных алгоритмов. Какой из них выбрать для решения конкретной задачи? Этот вопрос очень тщательно прорабатывается в программировании.

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

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

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

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

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

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

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.