Как найти асимптотическую оценку - Сайт, где вы сможете решить свои вопросы

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 19 июня 2018 года; проверки требуют 4 правки.

Асимптоти́чески норма́льная оце́нка — в математической статистике оценка, распределение которой стремится к нормальному распределению при увеличении размера выборки.

Определение[править | править код]

Пусть $X_{1},ldots ,X_{n},ldots$ — выборка из распределения $mathbb {P} _{theta }$ , зависящего от параметра .

Точечная оценка называется асимптотически нормальной с дисперсией ${displaystyle sigma ^{2}(theta )}$ , если

{displaystyle {sqrt {n}}left({hat {theta }}-theta right)to Z}

по распределению при

где ${displaystyle Zsim mathrm {N} left(0,sigma ^{2}(theta )right)}$ – нормальная случайная величина.

Замечание[править | править код]

Эквивалентно, оценка асимптотически нормальна, если

${displaystyle {frac {{sqrt {n}}left({hat {theta }}-theta right)}{sigma (theta )}}to {tilde {Z}}}$

по распределению при

где .

Свойства[править | править код]

Асимптотически нормальная оценка состоятельна.
При выполнении достаточно общих технических условий оценка метода моментов асимптотически нормальна.

Примеры[править | править код]

${displaystyle {hat {theta }}_{1}=2{bar {X}}}$

где – выборочное среднее, а

${displaystyle {hat {theta }}_{2}=X_{(n)}}$

где ${displaystyle X_{(n)}=max(X_{1},ldots ,X_{n})}$ .
Тогда оценка ${displaystyle {hat {theta }}_{1}}$ является асимптотически нормальной с дисперсией ${displaystyle sigma ^{2}(theta )=theta ^{2}/3}$ , а оценка ${displaystyle {hat {theta }}_{2}}$ не является асимптотически нормальной.

Источник

Войти на сайте МЭШ

Войдите с учетной записью ученика или учителя МЭШ,
чтобы получить доступ к личному кабинету.

Расчет асимптотической сложности

Расчет асимптотики – 1

Часто необходимо понимать насколько эффективен написанный код. Для этого обычно оценивают время выполнения и/или затрачиваемую память.
Для выражения этой оценки часто используют асимптотическую сложность (в дальнейшем будем считать, что времени, т.к. по сравнению с памятью значимых отличий нет)
Сложность зависит от переменных входных параметров и выражают ее как функцию, зависящую от размеров этих данных (подробнее в примере в конце теории).
Для оценки сложности нам интересно именно асимптотическое поведение этих функций (отсюда и короткое выражение – “асимптотика кода”), то есть когда входные данные довольно большого размера.
Поэтому используют так называемую О-нотацию. За этим стоит не самая простая математическая теория, в которую углубляться не будем. Желающие могут подробнее ознакомиться на википедии или других интернет-ресурсах.
Однако стоит запомнить, что асимптотику кода почти всегда указывают в этой самой нотации, поэтому стоит самим всегда так делать. На небольшом примере разберемся как примерно это делать.

Как очевидно из названия, функции записываются внутри скобок, обозначенных большой буквой “O”. Например: О(n), O(nm), O(log(c)), где как n, m, c или др. мы обозначаем потенциальные размеры входных данных.
Теперь о том, как саму асимптотику считать.
1) Для начала надо понять от размера каких данных зависит время выполнения программы. Сопоставим размеру этих данных переменные, в контексте которых и будем вычислять асимптотику. Обычно их обозначают буквами n, а затем m.
2) Далее выразим реальное время работы через эти переменные. Если некоторые части сложно посчитать точно, то оценивают приблизительно и сверху (то есть преувеличивают с запасом), т.к. предположить, что программа тратит больше ресурсов, чем на самом деле, не страшно, а вот обратная ситуация потенциально может приводить к проблемам.
3) После этого среди всех слагаемых возьмем самое “тяжелое”. Их может быть несколько, если их нельзя сравнить (например разные переменные, т.е. размеры разных входов, т.к. мы не знаем заранее что именно программа получит на вход). Далее опускаются константные множители у этих слагаемых (даже если изначально было, например, 100000n или 0.00001n, то остается только n) и после этого результат записывается в О-нотации.

Разберем небольшой пример.
Предположим, что у нас есть программа, которая принимает на вход массив целых чисел и сравнивает количество обменов, необходимых для сортировки пузырьком этого массива и сортировки слиянием.
Здесь время работы программы зависит только от входящего массива. Обозначим за n его размер.
Посчитаем реальное время работы. n итераций на считывание массива, сортировка пузырьком, которая в худшем случае будет использовать n*(n-1)/2 обменов (здесь нам важно учитывать именно худший случай), сортировка слиянием, время которой тяжело оценить точно, но оценим его сверху как 10*n*log(n) (т.к. мы знаем, что она работает за О(n*log(n)), но как уже было сказано, константы опускаются)
Итого примерное время работы: n + n*(n-1)/2 + 10*n*log(n) = n + n^2/2 – n/2 + 10*n*log(n). Довольно понятно, что 1ое и 3ее слагаемые здесь не являются определяющими. Вопрос лишь в том, что “тяжелее”, 2ое или 4ое.
Заметим, что при небольшом n, например, при n=4, 4ое слагаемое имеет на порядок большее значение, чем 2ое (8 против 80). Однако это не имеет никакого значения, как раз потому, что мы проводим асимптотический анализ, то есть предполагая, что входные данные довольно большого размера, например, n=1000000. При таком размере входных данных уже наглядно видно, насколько n^2/2 на самом деле превышает 10*n*log(n).
В итоге мы оставили самое “тяжелое” слагаемое n^2/2 и теперь проигнорируем его константный множитель 1/2. Таким образом, асимптотика данного алгоритма равна О(n^2).

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

Источник

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

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

Основные оценки роста, встречающиеся в асимптотическом анализе:

Ο (О-большое) – верхняя асимптотическая оценка роста временной функции;
Ω (Омега) – нижняя асимптотическая оценка роста временной функции;
Θ (Тета) – нижняя и верхняя асимптотические оценки роста временной функции.

Пусть n – величина объема данных. Тогда рост функции алгоритма f(n) можно ограничить функций g(n) асимптотически:

Обозначение	Описание
f(n) ∈ Ο(g(n))	f ограничена сверху функцией g с точностью до постоянного множителя
f(n) ∈ Ω(g(n))	f ограничена снизу функцией g с точностью до постоянного множителя
f(n) ∈ Θ(g(n))	f ограничена снизу и сверху функцией g

Например, время уборки помещения линейно зависит от площади этого самого помещения (Θ(S)), т. е. с ростом площади в n раз, время уборки увеличиться также в n раз. Поиск имени в телефонной книге потребует линейного времени Ο(n), если воспользоваться алгоритмом линейного поиска, либо времени, логарифмически зависящего от числа записей (Ο(log₂(n))), в случае применения двоичного поиска.

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

Под фразой «сложность алгоритма есть Ο(f(n))» подразумевается, что с увеличением объема входных данных n, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n).

Важные правила асимптотического анализа:

O(k*f) = O(f) – постоянный множитель k (константа) отбрасывается, поскольку с ростом объема данных, его смысл теряется, например:

O(9,1n) = O(n)

O(f*g) = O(f)*O(g) – оценка сложности произведения двух функций равна произведению их сложностей, например:

O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n²)

O(f/g)=O(f)/O(g) – оценка сложности частного двух функций равна частному их сложностей, например:

O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)

O(f+g) равна доминанте O(f) и O(g) – оценка сложности суммы функций определяется как оценка сложности доминанты первого и второго слагаемых, например:

O(n⁵+n¹⁰) = O(n¹⁰)

Подсчет количества операций – дело утомительное и, что важно, совсем не обязательное. Исходя из выше перечисленных правил, чтобы определить сложность алгоритма, не нужно, как мы это делали прежде, считать все операции, достаточно знать какой сложностью обладает та или иная конструкция алгоритма (оператор или группа операторов). Так, алгоритм, не содержащий циклов и рекурсий, имеет константную сложность O(1). Сложность цикла, выполняющего n итераций, равна O(n). Конструкция их двух вложенных циклов, зависящих от одной и той же переменной n, имеет квадратичную сложность O(n²).

Вот наиболее часто встречающиеся классы сложности:

O(1) – константная сложность;
О(n) – линейная сложность;
О(n^а) – полиномиальная сложность;
О(Log(n)) – логарифмическая сложность;
O(n*log(n)) – квазилинейная сложность;
O(2ⁿ) – экспоненциальная сложность;
O(n!) – факториальная сложность.

Источник

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

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

Например,
если оценивается эффективность алгоритма
сортировки числовой последовательности,
представленной одномерным массивом,
то в качестве параметра берется длина
массива n. Если рассматривается алгоритм
поиска на графе G(X, U), то в качестве
параметра берется либо число вершин
n=x,
либо число ребер m=U,
либо то и другое вместе.

Функция
f(n) является
функцией
порядка g(n) для
больших n (f(n)=O[g(n)]), если

Пример.
f(n)=3n⁵+100n⁴-4n²+6

f(n)=0(n⁵),
так как

Оценку
сложности обозначают буквой F. При этом
определяют асимптотическую оценку
сложности

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

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

Выделены
следующие оценки сложности алгоритмов:

1.
F(n)=O(n) – линейная оценка

F(n)=O[n
log(n)] – логарифмическая оценка
F(n)=O(n²)
– квадратичная оценка
F(n)=O(a₀n^k+a₁n^k+1+…+a_k)
– полиномиальная оценка
F(n)=O(aⁿ)
– экспоненциальная оценка
F(n)=O(n!)
– факториальная оценка
F(n)=O(nⁿ)
– гиперэкспоненциальная оценка

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

Ко второму классу
относятся алгоритмы, имеющие
экспоненциальную оценку сложности и
выше. Эти алгоритмы непригодны для
программирования, так как с увеличением
n функция F растет очень быстро.

Порядки сложности алгоритма

n	n²	n³	2ⁿ
1	1	1	2
10	100	1000	1024
15	225	3375	32768
20	400	8000	1048576
25	625	15625	33554432
30	900	27000	>10⁹

В таблице приведено
сравнение порядков сложности алгоритма.
Хорошо видно, как растет число шагов
при увеличении размерности задачи. Из
таблицы следует, что при n>20 алгоритмы
с экспоненциальной оценкой сложности
и выше не пригодны для программной
реализации.

Следует отметить,
что одним из основных недостатков
подобных оценок сложности является их
грубость. Действительно, пусть алгоритм
А₁решает задачу за 0.1n секунд, а
алгоритм А₂ – за 100n секунд, то есть
алгоритм А₂ работает в 1000 раз
быстрее алгоритма А₁.

Но оценка сложности
у них одинакова и равна О(n).

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Асимптотическая сложность алгоритмов встречается повсеместно. Доступно рассказываем, что это такое, где и как используется.

Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

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

Ты также будешь на связи с преподавателем и другими студентами.

В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂

Интересно, хочу попробовать

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

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

Разобравшись в принципе работы Big O Notation, вы сможете решить проблему оптимизации ваших программ и добиться максимально эффективного кода.

Сложности О(1) и O(n) самые простые для понимания.

О(1) означает, что данной операции требуется константное время. Например, за константное время выполняется поиск элемента в хэш-таблице, так как вы напрямую запрашиваете какой-то элемент, не делая никаких сравнений. То же самое относится к вызову i-того элемента в массиве. Такие операции не зависят от количества входных данных.

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

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

Например, если у вас есть отсортированный массив, насчитывающий 8 элементов, в худшем случае вам понадобится сделать Log_2(8)=3 сравнений, чтобы найти нужный элемент.

Рассмотрим отсортированный одномерный массив с 16 элементами:

Допустим, нам нужно найти число 13.

Мы выбираем медиану массива и сравниваем элемент под индексом 7 с числом 13.

Так как наш массив отсортирован, а 16 больше, чем 13, мы можем не рассматривать элементы, которые находятся под индексом 7 и выше. Так мы избавились от половины массива.

Дальше снова выбираем медиану в оставшейся половине массива.

Сравниваем и получаем, что 8 меньше, чем 13. Уменьшаем массив вдвое, выбираем элемент посередине и делаем еще одно сравнение. Повторяем процесс, пока не останется один элемент в массиве. Последнее сравнение возвращает нужный элемент. Лучшее развитие событий – если первая выбранная медиана и есть ваше число. Но в худшем случае вы совершите log_2(n) сравнений.

Сложность O(n*log n) можно представить в виде комбинации O(log n) и O(n). Такую сложность можно получить, если в вашей программе есть один for-цикл, который содержит еще один for-цикл. То есть нестинг циклов, один из которых работает за O(log n), а другой – за O(n).

for(int i = 0; i < n; i++) //выполняется n раз
  for(int j = 1; j < n; j = j * 2) // выполняется blogs раз
    print “hello"; //константное время

Сложность O(n^2) встречается довольно часто в алгоритмах сортировки. Ее легко можно получить, если в программе имплементировать нестинг двух for-циклов, работающих в O(n).

Например:

for(int i = 0; i < n; i++) // выполняется n раз
  for(int j = 0; j < n; j++) //выполняется n раз
    print “hello”; // константно

То же самое произойдет, если вам надо будет пройтись по элементам двумерного массива.

Алгоритмы, которые можно описать с помощью нотации O(n^2 + n + 3) или O(n^2-100000), или даже O(n^2 + 100000000) все равно считаются квадратными. При большом количестве входных данных только наибольшая степень n является важной. Константы и коэффициенты обычно не берут во внимание. То же самое касается линейных и логарифмических функций. O( n +1000) и O(1000*n) все равно будут работать в O(n).

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

Почерпнули для себя что-то новое? Делитесь тем, что мы могли упустить 😉

Источник

Определение[править | править код]

Замечание[править | править код]

Свойства[править | править код]

Примеры[править | править код]

Расчет асимптотической сложности

Расчет асимптотики – 1

Порядки сложности алгоритма

Почерпнули для себя что-то новое? Делитесь тем, что мы могли упустить 😉

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

Как найти угол сечения параллелепипеда

Как найти масштаб шрифта

Как найти на карте где находится абонент

Добавить комментарий Отменить ответ