Пересмотр сумм Ландау

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

Теперь, здесь наш рецидивы гуру JeffE делает в основном это:

$\qquad \displaystyle \sum_{i=1}^n \Theta\left(\frac{1}{i}\right) = \Theta(H_n)$

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

$\qquad \displaystyle \sum_{i=1}^n c_i \cdot \frac{1}{i} \leq c \cdot H_n$ .

Теперь, как мы вычисляем $c$ из $c_1, \dots, c_n$ ? Ответ, я считаю, что мы не можем: $c$ уже связан для все $n$ , но мы получаем больше $c_i$ в $n$ растет. Мы ничего о них не знаем; $c_i$ может очень хорошо зависеть от $i$ , поэтому мы не можем принять границу: конечное $c$ может не существовать.

Кроме того, есть тонкий вопрос о том, какая переменная переходит в бесконечность с левой стороны - $i$ или $n$ ? Обе? Если $n$ (для совместимости), что означает $\Theta(1/i)$ , зная, что $1 \leq i \leq n$ ? Означает ли это не только $\Theta(1)$ ? Если это так, мы не можем связать сумму лучше, чем $\Theta(n)$ .

Так, где это оставляет нас? Это явная ошибка? Тонкий? Или это просто обычное злоупотребление нотации , и мы не должны смотреть на $=$ знаков , как это один из контекста? Можем ли мы сформулировать (строго) правильное правило для оценки (определенных) сумм членов Ландау?

Я думаю, что главный вопрос: кто ? Если мы посчитаем его постоянным (поскольку он находится в пределах суммы), мы можем легко построить контрпримеры. Если оно не постоянное, я понятия не имею, как его читать. $i$

terminology asymptotics landau-notation Рафаэль
источник

Этот вопрос по математике. Хорошее чтение об арифметике с терминами Ландау в целом.

Рафаэль

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

\in

$\in$

Θ

$\Theta$

c = min (c_{1}, c_{2}, \dots, c_{n})

$c = \min(c_1, c_2, \cdots, c_n)$

C = max (c_{1}, c_{2}, \dots, c_{n})

$C = \max(c_1, c_2, \cdots, c_n)$

user834

Держись, Баки. Я не написал никакого суммирования с тэтой. Я написал повторение с тэтой в нем. Вы действительно интерпретируете повторение " " как что-то отличное от "Есть функция такой, что "?

t (n) = Θ (1 / n) + t (n - 1)

$t(n) = \Theta(1/n) + t(n-1)$

f \in Θ_{x \to \infty} (x \mapsto 1 / x)

$f \in \Theta_{x\to \infty}(x\mapsto 1/x)$

t (n) = f (n) + t (n - 1)

$t(n) = f(n) + t(n-1)$

Джефф

@ Рафаэль Нет, повторение не математически совпадает с суммой, именно по той причине, которую вы описываете! Повторение содержит ровно один тэта-термин, который однозначно относится к одной функции.

Джефф

Это не очень интуитивно понятно - я категорически не согласен, но я думаю, что это вопрос вкуса и опыта.

Джефф

Ответы:

Выглядит правильно для меня в следующем соглашении:

$S_n = \sum_{k=1}^{n} \Theta(1/k)$ - удобное обозначение для

Существует (как ) такой, что $f(x) \in \Theta(1/x)$ $x \to \infty$

$S_n = \sum_{k=1}^{n} f(k)$ .

Таким образом, (или с пометкой в этом ответе ), которую вы получите, на самом деле не зависят от . $c_i$ $c_k$ $k$

При такой интерпретации действительно верно, что . $S_n = \Theta(H_n)$

Фактически, в ответе Джеффа он показывает, что где , поэтому это согласуется с приведенной выше интерпретацией. $T(k+1) = f(k) + T(k)$ $f \in \Theta(1/k)$

Кажется, что путаница возникает из-за того, что мы мысленно "разворачиваем" и предполагаем разные функции для каждого случая ... $\sum$ $\Theta$

Арьябхата
источник

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

Θ

$\Theta$

k

$k$

n

$n$

Рафаэль

@ Рафаэль: Кажется бессмысленным развернуть и затем разрешить разные : константы будут зависеть от переменной! и это становится неправильным использованием , предполагая, что переменная равна (или в ответе выше). Даже если мы предположим, что переменная равна , она все равно выглядит для меня бессмысленно.

f_{i}

$f_i$

Θ

$\Theta$

Θ

$\Theta$

i

$i$

k

$k$

n

$n$

Арьябхата

В принципе, каждый может иметь свою собственную постоянную, но в данном контексте вы описали , это ясно , что каждый вовсе не имеет свою собственную константу.

Θ

$\Theta$

Θ

$\Theta$

Джефф

@ Джефф: Точно. Мы можем иметь несколько с их собственными константами, если константы действительно постоянны :-)

Θ

$\Theta$

Aryabhata

@JeffE Так почему бы тебе просто не написать, что ты имеешь в виду, а предпочесть что-то неоднозначное / неправильное? Обратите внимание, что мой обновленный ответ теперь предлагает способ сделать это. Буду признателен за комментарии по этому поводу; отрицательные мотивы без причины не помогают мне понять, почему люди, кажется, отвергают мою точку зрения.

Рафаэль

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

Чтобы развить это формально, что делает

$\qquad \displaystyle S_n \in \sum_{i=1}^n \Theta(f(i)) \qquad \qquad\qquad (1)$

на самом деле означает? Теперь я предполагаю, что эти позволяют - не - бесконечности; если мы позволим , то каждая такая сумма оценивается как (если слагаемые не зависят от и, следовательно, постоянны), что явно неверно. Вот первая распродажа, которую мы придаем грубым вещам: связан (и постоянен) внутри суммы, но мы все же позволим ей уйти в бесконечность? $\Theta$ $i$ $n$ $n \to \infty$ $\Theta(n)$ $n$ $i$

Переведя (для верхней границы нижняя оценка работает аналогично), получим $(1)$

$\qquad \displaystyle \exists f_1, \dots, f_n \in \Theta(f).\ S_n \leq \sum_{i=1}^n f_i(i)$

Теперь ясно, что сумма и параметр связаны между собой: мы можем легко определить чтобы они использовали в качестве константы. В примере из вопроса мы можем определить и иметь $i$ $i$ $f_i$ $i$ $f_i(j) = i \cdot \frac{1}{j} \in \Theta(1/j)$

$\qquad \displaystyle \sum_{i=0}^n f_i(i) "=" \sum_{i=0}^n \Theta(1/j) = \sum_{i=0}^n \Theta(1/i)$

но исходная сумма явно не оценивается как что-то в . Теперь замена на - это только переименование - в может показаться странным, потому что не зависит от соответственно. сумма, но если мы возражаем против этого сейчас , мы никогда не должны были бы использовать внутри в первую очередь (так как он содержит ту же странность). $\Theta(H_n) = \Theta(\log n)$ $j$ $i$ $\Theta$ $i$ $n$ $i$ $\Theta$

Обратите внимание, что мы даже не использовали, что также может зависеть от . $f_i$ $n$

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

Мне пришло в голову, что мы можем также написать именно то , что мы имеем в виду, и все еще использовать удобные термины Ландау. Мы знаем, что все слагаемые происходят от одной общей функции, подразумевая, что асимптотические оценки используют одни и те же константы. Это теряется, когда мы помещаем в сумму. Так что давайте не будем помещать это туда и писать $\Theta$

$\qquad \displaystyle \sum_{i=1}^n \frac{2i - 1}{i(i+1)} \in \Theta\left(\sum_{i=1}^n \frac{1}{i}\right) = \Theta(H_n)$

вместо. Помещение за пределы суммы приводит к $\Theta$

математически правильное утверждение и
простой термин внутри в мы можем легко иметь дело с (это то , что мы хотим здесь, не так ли?). $\Theta$

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

Рафаэль
источник

Рассмотрим . Я могу определить (используя в качестве константы), поэтому по вашим рассуждениям, верно? Но эта сумма .

\sum_{i}^{n} i

$\sum_i^n i$

f_{i} (n) = i

$f_i(n)=i$

i

$i$

\sum_{i}^{n} i = \sum_{i}^{n} O (1) = O (n)

$\sum_i^n i = \sum_i^n O(1) = O(n)$

O (n^{2})

$O(n^2)$

Xodarap

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

Θ

$\Theta$

i

$i$

n

$n$

n

$n$

Рафаэль

Я не связываю их с , я просто использую тот факт, что . (И я предполагаю также тот факт, что .)

n

$n$

\sum_{i}^{n} k = n k

$\sum_i^n k = nk$

n O (f) = O (n f)

$nO(f)=O(nf)$

Xodarap

@Xodarap: Но вы не имеете один , но один в слагаемым. Если базовые функции используют (как постоянный множитель), вы должны расширить это, и сумма в итоге окажется правильной. Итак, по моим рассуждениям предложенное вами правило суммирования не работает так, как вы пишете.

f

$f$

f_{i}

$f_i$

f_{i}

$f_i$

i

$i$

Рафаэль

Если у меня есть последовательность , каждая из них - (при условии, что они не увеличиваются по мере развития серии). Вы сказали бы, что добавление из них сгенерирует сумму ? Какая разница, если вместо того, чтобы быть константами, я описываю их как постоянные функции ?

5, 1, 3, 2, \dots

$5,1,3,2,\dots$

O (1)

$O(1)$

n

$n$

O (n)

$O(n)$

f_{1} (x) = 5, f_{2} (x) = 1, \dots

$f_1(x)=5,f_2(x)=1,\dots$

Xodarap

-1

Если каждое является константой, то существует некоторый такой, что . Так ясно Та же идея для маленьких о. $c_i$ $c_{max}$ $\forall c_i: c_i\leq c_{max}$

\sum c_{i} f (i) \leq \sum c_{m a x} f (i) = c_{m a x} \sum f (i) = O (\sum f (i))

$\sum c_i f(i) \leq \sum c_{max} f(i) = c_{max} \sum f(i) = O\left(\sum f(i)\right)$

Я думаю, что проблема здесь в том, что . Это (поскольку нет такого, что ), поэтому общая сумма будет . И каждый член равен , что означает общую сумму . Таким образом, нет жестких границ от этого метода. $1/i\not=\Theta(1)$ $o(1/n)$ $\epsilon$ $\forall i: 1/i>\epsilon$ $no(1/n)=o(1)$ $O(1)$ $O(n)$

Я думаю, что ваши вопросы:

Является ли приемлемым ограничение , делающее маленькое o каждого члена и большое o каждого члена, а затем умножение на ? (Ответ: да) $\sum_i^n f(i)$ $n$
Есть ли лучший метод? (Ответ: не то, что я знаю.)

Надеюсь, кто-то еще может ответить # 2 более четко.

РЕДАКТИРОВАТЬ: глядя на ваш вопрос еще раз, я думаю, что вы спрашиваете

$\sum_i^n \Theta(f(n)) = \Theta(nf(n))$ ?

На что ответ да. В этом случае, однако, каждый термин не является чего-либо, поэтому такой подход разваливается. $\Theta$

РЕДАКТИРОВАТЬ 2: Вы говорите «рассмотрите , тогда нет ». Однозначно верно. Если вы говорите, что является непостоянной функцией , то она, по определению, непостоянна. $c_i=i$ $c_{max}$ $c_i$ $i$

Обратите внимание, что если вы определите это таким образом, то - это не , а . В самом деле, если вы определили «константа» для обозначения «любой функции », то любые две функции отличаются на «константу»! $c_i i$ $\Theta(i)$ $\Theta(i^2)$ $i$ $i$

Возможно, это более простой способ думать об этом: у нас есть последовательность . Какой самый маленький термин в этой последовательности? Ну, это будет зависеть от . Поэтому мы не можем считать термины постоянными. $1,\frac{1}{2},\dots,\frac{1}{n}$ $n$

(Специалисты по компьютерам часто лучше знакомы с big-O, поэтому было бы более интуитивно спрашивать, имеет ли постоянный наибольший термин.) $1,\dots,n$

Чтобы предоставить доказательство: пусть будет наименьшим значением в диапазоне . Тогда $f(i_{min})$ $f(i)$ $1,\dots,n$

\sum_{i}^{n} f (i) \geq \sum_{i}^{n} f (i_{m i n}) = n f (i_{m i n}) = n o (f (n))

$\sum_i^n f(i) \geq \sum_i^n f(i_{min}) = n f(i_{min}) = n o(f(n))$

Аналогичное доказательство может быть сделано для верхней границы.

Наконец, вы пишете, что и в качестве доказательства приводите . Фактически это является контр-доказательством: если «больше», чем , то оно не может быть «меньше», чем , что необходимо для того, чтобы он был . Так что это не может быть . $H_n = o(n)$ $H_n = \Theta(\log n)$ $H_n$ $n$ $\log n$ $\Theta(\log n)$ $o(n)$

Xodarap
источник

1) «..то-то есть такой, что ...» - нет, нет. Рассмотрим с . 2) «Я не думаю, что » - 3) . Это - это неправильно. Как , . 4) «(Ответ: да)» - пока я не вижу формального доказательства этого факта, я в это не верю. Кроме того, «умножение на » не то, что произошло в выставленном случае.

c_{m a x}

$c_{max}$

(c_{i})_{i \in N}

$(c_i)_{i \in \mathbb{N}}$

c_{i} = i

$c_i = i$

H_{n} = o (n)

$H_n=o(n)$

H_{n} \in Θ (\ln n)

$H_n \in \Theta(\ln n)$

1 / i \neq Θ (1)

$1/i\not=\Theta(1)$

o (1 / n)

$o(1/n)$

1 / i \geq 1 / n

$1/i \geq 1/n$

1 / i \in Ω (1 / n)

$1/i \in \Omega(1/n)$

n

$n$

Рафаэль

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

f

$f$

n

$n$

Рафаэль

Я до сих пор не понимаю, что вы говорите, поэтому я рад, что вы поняли это :-)

Xodarap