Что означает слово «масштабируемость» с точки зрения Big O?

Question

Что означает слово «масштабируемость» с точки зрения Big O?

исчисление
алгоритмы
асимптотика
Математика
реальный анализ
вычислительная сложность

математик

Я встречал множество источников, утверждающих, что:

Бенчмарки оценивают время выполнения, Big O оценивает масштабируемость.

Они объяснили значение «масштабируемости» следующим образом:

Масштабируемость говорит вам, как масштабируется время выполнения вашего алгоритма. Значение, как время вычислений увеличивается, когда вы увеличиваете размер ввода. Для $O\left(n\right)$ вы удваиваете размер входных данных и удваиваете время вычислений. Для $O\left(n^2\right)$ вы удваиваете размер входных данных, в четыре раза увеличиваете время вычислений и так далее.

Это означает, что если ваш алгоритм принимает $f(n)$ шагов в худшем случае и $f \in O\left(n^2\right)$ , то отношение $\frac{f(2n)}{f(n)}$ равно $4$ при достаточно больших значениях $n$ (вы удваиваете размер ввода и в четыре раза увеличиваете время вычислений).

И в этом было так много смысла. Но недавно мне показали контрпример, доказывающий, что приведенное выше утверждение просто неверно. Рассмотрим функцию $f\left(n\right) = n^2\left(\cos (n) + 2\right)$ . Мы видим, что $f \in O\left(n^2\right)$ . Кроме того, для тех из вас, кто хочет заметить, что $O\left(n^2\right)$ люди обычно имеют в виду $\Theta\left(n^2\right)$ мы можем легко заметить, что $f \in \Theta\left(n^2\right)$ также:

Но $f$ не масштабируется как $n^2$ в том смысле, что мы не можем утверждать, что $\frac{f(2n)}{f(n)}$ равно $4$ (даже приблизительно) при любых (даже больших) значениях n. Я имею в виду, если мы знаем, что $f \in O\left(n^2\right)$ и если мы удвоим размер входных данных, мы не сможем просто вчетверо увеличить время вычислений, потому что это неправильно.

Я сделал сюжет $\frac{f(2n)}{f(n)}$ для вас, чтобы визуализировать это:

Не похоже, что это соотношение стремится к 4.

Итак, мои вопросы:

Почему люди так объясняют значение «масштабируемости»? Есть ли причина для этого или они технически неверны?
Что же тогда означает это слово «масштабируемость»? Что же тогда оценивает Big O (если не «масштабируемость»)?

В общем, я ищу чисто математическое объяснение этому. Но не усложняйте, пожалуйста: я все еще изучаю исчисление одной переменной. Спасибо всем заранее!

Фшрайк

Проблема в том, что ограничений технически не существует. Ясно, что

f

$f$ является

Θ (n^{2})

$\Theta(n^2)$ по идее ограниченности, но в определении предела отмечается, что, хотя отношение функций определенно конечно и не равно нулю, предел косинуса не определен на бесконечности (колебание). Я не уверен здесь, но, может быть, даже есть основания сказать, что

f

$f$ не является

O (n^{2})

$O(n^2)$ вообще по этому признаку.

математик

@FShrike, спасибо за комментарий. Но

f \in O (n^{2})

$f \in O\left(n^2\right)$ по определению Большого О.

Фшрайк

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

Ян

1. Примеры, подобные этому, где

f \in Θ (g)

$f \in \Theta(g)$ но

f / g

$f/g$ является колебательным, как

n \to \infty

$n \to \infty$ в реальной практике не распространены. Навскидку единственное, что приходит на ум при таком поведении, — это БПФ, и даже оно имеет фиксированное масштабирование, если вы работаете только со степенями двойки. 2. Масштабируемость по-прежнему грубо выражает скорость роста функции, насколько больше она становится, когда вы увеличиваете ввод на кучу. Большая Тета по-прежнему дает вам это грубое описание. Но ты прав, что просто зная, скажем,

f \in Θ (n^{2})

$f \in \Theta(n^2)$ не говорит тебе этого

f (2 n) / f (n)

$f(2n)/f(n)$ будет стремиться к

4

$4$ .

Ян

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

n

$n$ почти кратно

2 π

$2\pi$ "; типичные случаи будут означать "сравните две задачи, где

n

$n$ близко к нечетному кратному

π / 2

$\pi/2$ ".

математик

@Ian, спасибо за комментарий! В последнем комментарии вы утверждаете, что

n^{2} (c o s (n) + 2)

$n^2\left(cos(n) + 2\right)$ не может быть худшим случаем, потому что

3 n^{2}

$3n^2$ еще хуже?

Ян

Я имею в виду, если фактическое время выполнения

n^{2} (\cos (n) + 2)

$n^2(\cos(n)+2)$ тогда худший случай для

n

$n$ на одном интервале длины

2 π

$2\pi$ будет, когда

n

$n$ является кратным

2 π

$2\pi$ и в этом случае у вас есть

3 n^{2}

$3n^2$ .

математик

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

f (n)

$f(n)$ которые представляют собой количество шагов, предпринятых для наихудшего ввода длины

n

$n$ . Но как можно пойти еще дальше и указать отдельные точки вида

2 π k

$2πk$ для представления поведения в худшем случае, если у нас уже есть функция

f

$f$ что представляет наихудший случай поведения?

Ян

я имею в виду, что

n

$n$ - фактический размер ввода и

f (n)

$f(n)$ фактическое время выполнения и

f (n)

$f(n)$ колеблется, потому что каким-то образом числа близки к нечетным целым числам, кратным

π

$\pi$ с ними гораздо проще обращаться, чем с числами, близкими к четным целым кратным

π

$\pi$ (сама необычная ситуация). Так что худшее

n

$n$ заданного "порядка величины" - это близкие

2 π k

$2\pi k$ , поэтому, если вы хотите изучить рост в худшем случае, вы смотрите на

n = r o u n d (2 π k), k = 1, 2, \dots

$n=\mathrm{round}(2\pi k),k=1,2,\dots$ (т.е.

6, 13, 19

$6,13,19$ и т. д.)

математик

@Ian, но ты согласен, что когда мы рассматриваем функцию

f (n)

$f(n)$ это уже означает каждый ввод

n

$n$ должно быть худшим? Потому что

f (n)

$f(n)$ по своему определению принимает только наихудшие входные данные

Ян

Нет, я говорю о локально худших значениях

n

$n$ (что обычно даже не стоит учитывать, но в вашем случае это важно).

Ответы (2)

Что означает слово «масштабируемость» с точки зрения Big O?

Проблема в том, что ограничений технически не существует. Ясно, что $f$ является $\Theta(n^2)$ по идее ограниченности, но в определении предела отмечается, что, хотя отношение функций определенно конечно и не равно нулю, предел косинуса не определен на бесконечности (колебание). Я не уверен здесь, но, может быть, даже есть основания сказать, что $f$ не является $O(n^2)$ вообще по этому признаку.
@FShrike, спасибо за комментарий. Но $f \in O\left(n^2\right)$ по определению Большого О.
Идея масштабируемости смешивается с осцилляциями, но из определений пределов нельзя сделать немедленный вывод о масштабируемости (хотя теперь я вспоминаю, что в определениях пределов используются верхняя и нижняя границы, чтобы обойти идею о том, что обычные пределы не существуют, поэтому я принимаю Верните часть того, что я сказал в предыдущем комментарии)
1. Примеры, подобные этому, где $f \in \Theta(g)$ но $f/g$ является колебательным, как $n \to \infty$ в реальной практике не распространены. Навскидку единственное, что приходит на ум при таком поведении, — это БПФ, и даже оно имеет фиксированное масштабирование, если вы работаете только со степенями двойки. 2. Масштабируемость по-прежнему грубо выражает скорость роста функции, насколько больше она становится, когда вы увеличиваете ввод на кучу. Большая Тета по-прежнему дает вам это грубое описание. Но ты прав, что просто зная, скажем, $f \in \Theta(n^2)$ не говорит тебе этого $f(2n)/f(n)$ будет стремиться к $4$ .
В частности, в контексте теории сложности люди обычно интересуются либо наихудшими, либо типичными случаями. Худшие случаи в вашей ситуации будут означать «сравните две задачи, где $n$ почти кратно $2\pi$ "; типичные случаи будут означать "сравните две задачи, где $n$ близко к нечетному кратному $\pi/2$ ".
@Ian, спасибо за комментарий! В последнем комментарии вы утверждаете, что $n^2\left(cos(n) + 2\right)$ не может быть худшим случаем, потому что $3n^2$ еще хуже?
Я имею в виду, если фактическое время выполнения $n^2(\cos(n)+2)$ тогда худший случай для $n$ на одном интервале длины $2\pi$ будет, когда $n$ является кратным $2\pi$ и в этом случае у вас есть $3n^2$ .
@Ian, но, насколько я понимаю, фактического времени выполнения не будет, если вы сначала не укажете случай (худший, средний, лучший). С этого момента, когда вы классифицировали его как наихудший, вы выводите функцию $f(n)$ которые представляют собой количество шагов, предпринятых для наихудшего ввода длины $n$ . Но как можно пойти еще дальше и указать отдельные точки вида $2πk$ для представления поведения в худшем случае, если у нас уже есть функция $f$ что представляет наихудший случай поведения?
я имею в виду, что $n$ - фактический размер ввода и $f(n)$ фактическое время выполнения и $f(n)$ колеблется, потому что каким-то образом числа близки к нечетным целым числам, кратным $\pi$ с ними гораздо проще обращаться, чем с числами, близкими к четным целым кратным $\pi$ (сама необычная ситуация). Так что худшее $n$ заданного "порядка величины" - это близкие $2\pi k$ , поэтому, если вы хотите изучить рост в худшем случае, вы смотрите на $n=\mathrm{round}(2\pi k),k=1,2,\dots$ (т.е. $6,13,19$ и т. д.)
@Ian, но ты согласен, что когда мы рассматриваем функцию $f(n)$ это уже означает каждый ввод $n$ должно быть худшим? Потому что $f(n)$ по своему определению принимает только наихудшие входные данные
Нет, я говорю о локально худших значениях $n$ (что обычно даже не стоит учитывать, но в вашем случае это важно).

Особенно Лайм · Answer 1

Этот (очень красивый) пример весьма необычен — на практике функции $f(n)$ которые на самом деле возникают и $\Theta(n^2)$ обычно удовлетворяют $f(n)/n^2$ стремится к некоторому положительному пределу (а не просто отграничивается от $0$ и $\infty$ ). Итак, упрощенная версия масштабируемости — $\lim_{n\to\infty}f(2n)/f(n)$ - существует и есть $4$ .

Тем не менее, даже для вашей функции есть разумный смысл, в котором удвоение $n$ , в среднем увеличивается $f(n)$ с коэффициентом $4$ . Что мы можем подразумевать под «в среднем»? Ну, чтобы взять среднее, вам нужно удвоить более одного раза. Если вы удвоите дважды, чтобы перейти от $f(n)$ к $f(4n)$ тогда средний коэффициент масштабирования двух удвоений, который имеет смысл, представляет собой среднее геометрическое (потому что вы пытаетесь приблизиться к геометрическому росту), т.е. $\sqrt{f(4n)/f(n)}$ . Теперь и это не стремится к пределу, но $\sqrt[k]{f(2^kn)/f(n)}$ , то есть (геометрический) средний коэффициент масштабирования от $k$ удвоения, стремится к пределу, поскольку $k\to\infty$ , который $4$ .

Спасибо за ответ! Но не похоже ли, что мы только что придумали из воздуха способ оправдать первоначальное значение слова «масштаб»?
Кроме того, почему среднее арифметическое хуже в этом случае? Мне это кажется столь же разумным, как и среднее геометрическое.
@mathgeek Это в основном потому, что если мы масштабируем с коэффициентом $x$ а затем масштабировать с коэффициентом $y$ , то общий масштаб равен $xy$ нет $x+y$ . Идея получения среднего значения заключается в том, «какой список $k$ одинаковые вещи больше всего походили бы на этот список $k$ разные вещи?» Здесь масштабирование $k$ разные факторы должны давать тот же общий результат, что и масштабирование по «среднему» фактору $k$ раз, и это работает, если под «средним» подразумевается среднее геометрическое.
Я не мог ожидать объяснения лучше, чем это! Спасибо! Но я с трудом могу представить людей, думающих обо всех этих вычислениях, когда они говорят, что время выполнения растет «порядка квадрата размера ввода». Не могли бы вы пояснить, о чем думают такие люди (что они на самом деле имеют в виду), говоря это, и правомерно ли вообще так говорить об этом? $f$ , данный $f \in O(n^2)$ ?
Это все еще правильно, просто он может дать сбой на уровне сравнения двух конкретных значений функции, если $f$ странно. И я действительно не могу не подчеркнуть, насколько нетипичен ваш пример в реальном асимптотическом анализе, особенно в теории сложности.
@ Jean-ClaudeArbaut Я не понимаю, почему это вводит в заблуждение. Я конкретно говорю о примере OP, который (как конкретно говорит OP) является примером функции, которая $\Theta(n^2)$ но, похоже, не масштабируется, как ожидалось. Если вы знаете, что функция $O(n^2)$ , то во втором абзаце в принципе нужно заменить $\lim$ к $\limsup$ и $4$ к $\leq 4$ .

Ленивый · Answer 2

Ленивый

Символы Ландау не заботятся о точном поведении функций. $f\in O(g)$ означает, что для больших $x$ у нас есть $f$ весы в лучшем случае так плохо, как $g$ в смысле $f$ ограничен кратным $g$ .

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

математик

Спасибо за ответ! Но если вы посмотрите на мой первый сюжет, вы заметите, что

f

$f$ масштабируется хуже, чем

n^{2}

$n^2$ с интервалом

(10; 12)

$\left(10;\ 12\right)$ например. Таким образом, он не «масштабируется МАКСИМАЛЬНО так плохо, как

g

$g$ ".

Фшрайк

@mathgeek Мы рассматриваем ограничения как

n \to \infty

$n\to\infty$ в стандартном определении, а не как

n \to (10, 12)

$n\to(10,12)$

математик

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

n

$n$ (вы можете сделать его настолько большим, насколько хотите).

Ленивый

@mathgeek Это одно из предостережений с нотацией Ландау. Масштабирование — это термин, который мы используем для аргумента, который становится большим, но мы не указываем, насколько большим он будет. Обратите внимание, что если

f

$f$ является непрерывным и

g

$g$ непрерывно и нигде

0

$0$ то на любом отрезке мы всегда найдем

c

$c$ с

f \leq c g

$f\leq cg$ на этом интервале (мин./макс. конт. функций на компактах). И даже тогда определение символов Ландау всегда уточняет: Для всех

x > x_{0}

$x>x_0$ для некоторого произвольного

x_{0}

$x_0$ . Таким образом, в основном мы не заботимся о конечных значениях.

Ленивый

Вы можете думать об этом так: если

f \in O (g)

$f\in O(g)$ тогда асимптотика

lim sup \frac{f (x)}{g (x)}

$\limsup\frac{f(x)}{g(x)}$ конечно. Если

f \in Θ (g)

$f\in\Theta(g)$ тогда также

0 < lim inf \frac{f (x)}{g (x)}

$0<\liminf \frac{f(x)}{g(x)}$ .

математик

Да, ваш последний комментарий - это определение, но, к сожалению, оно не объясняет значение слова «шкала» и почему оно имеет смысл в свете моего опубликованного вопроса.

Ленивый

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

n

$n$ лучшие алгоритмы, которые работают без больших предположений, имеют порядок

n \log n

$n\log n$ сравнения. Поэтому, если я увеличу размер своего списка, требуемое усилие увеличится чуть больше, чем линейно, но меньше, чем квадратично. Конечно, есть несколько вещей, которые вы можете рассмотреть: В лучшем случае? Худший случай? Средний случай?

математик

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

O (\log n)

$O\left(\log n\right)$ время. Не могли бы вы уточнить, что вы подразумеваете под «квадратичным увеличением»? Пожалуйста, имейте в виду пример неправильного объяснения «квадратичного увеличения», который я дал в своем вопросе.

Что означает слово «масштабируемость» с точки зрения Big O?

математик

Фшрайк

математик

Фшрайк

Ян

Ян

математик

Ян

математик

Ян

математик

Ян

Ответы (2)

Особенно Лайм

математик

математик

Особенно Лайм

математик

Ян

Особенно Лайм

Ленивый

математик

Фшрайк

математик

Ленивый

Ленивый

математик

Ленивый

математик

время работы алгоритма с учетом временной сложности

Сложность алгоритма — цикл for внутри цикла while; уменьшается в 2 раза

Как вычислить значение многомерного предела?

Какова временная сложность при равномерной выборке записей bbb без замены записей nnn?

Ожидаемое время быстрой сортировки

Спивак использует свойство в собственном доказательстве?

Слабая абсолютная непрерывность мер

Контрпример к «дифференцируемое подразумевает непрерывное»?

Интегралы Дарбу с делением пополам

Доказательство существования производной при заданном пределе f'