Вопросы с тегом «notation»

91
Как узнать, какую нотацию анализа сложности времени использовать?

В большинстве вводных классов алгоритмов вводятся нотации, такие как (Big O) и , и студент, как правило, учится использовать одну из них для определения сложности времени.ΘОOOΘΘ\Theta Однако есть и другие обозначения, такие как , и . Существуют ли какие-либо конкретные сценарии, в которых одна...

47
Порядок определения роста от Reynolds & Tymann

Я читаю книгу под названием « Принципы информатики» (2008) Карла Рейнольдса и Пола Тиманна (опубликована в «Схемах Шаума»). Во второй главе представлены алгоритмы с примером последовательного поиска, который просто перебирает список имен и возвращает TRUE, если в списке найдено данное имя. Автор...

44
Что означает ?

Это основной вопрос, но я думаю, что совпадает с , поскольку больший член должен доминировать при переходе к бесконечности? Кроме того, это будет отличаться от O (\ min (m, n)) . Это правильно? Я продолжаю видеть это обозначение, особенно при обсуждении алгоритмов графа. Например, вы обычно видите:...

35
Сортировка функций по асимптотическому росту

Предположим, у меня есть список функций, например nloglog(n),2n,n!,n3,nlnn,…nlog⁡log⁡(n),2n,n!,n3,nln⁡n,…\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots Как мне отсортировать их асимптотически, т.е. после отношения, определенного f≤Og⟺f∈O(g)f≤Og⟺f∈O(g)\qquad f \leq_O g \iff f \in O(g) , при...

28
Почему пустой тип C не аналогичен пустому / нижнему типу?

Википедия, а также другие источники, которые я обнаружил в списке voidтипа C как тип единицы, а не пустой тип. Мне кажется, что это сбивает с толку, так как мне кажется, что оно voidлучше подходит под определение пустого / нижнего типа voidНасколько я могу судить, ценности не обитают . Функция с...

24
Считается ли O (mn) «линейным» или «квадратичным» ростом?

Если бы у меня была функция с временной сложностью O ( mn ), где m и n - размеры двух ее входов, мы бы назвали ее временную сложность «линейной» (поскольку она линейна как по m, так и по n ) или «квадратичной» ( так как это продукт двух размеров)? Или что-то другое? Мне кажется, что называть его...

20
Изменение переменных в рекуррентных отношениях

В настоящее время я изучаю введение в алгоритмы (CLRS) и есть один конкретный метод, который они описывают в книге для решения рекуррентных отношений. Следующий метод может быть проиллюстрирован на этом примере. Предположим, у нас есть рецидив T( n ) = 2 Тл( н--√) + журналNT(n)=2T(n)+log⁡nT(n) =...

20
Обоснование пренебрежения постоянными факторами в Big O

Много раз, если сложности имеют константы, такие как 3n, мы пренебрегаем этой константой и говорим O (n), а не O (3n). Я не могу понять, как мы можем пренебречь такими трехкратными изменениями? Некоторые вещи меняются в 3 раза быстрее, чем другие! Почему мы пренебрегаем этим фактом?...

18
Что такое дробно-подобная запись в «дискретной математике» для формальных правил?

В статье «Бесконфликтный реплицированный тип данных JSON» я встретил эту запись для формального определения «правил»: Как называется эта запись? Как мне это прочитать? Например: DOCправило не имеет ничего в своем «числитель» - почему? то EXECи GETправила , по всей видимости, имеют два отдельных...

17
Какова цель использования NIL для представления нулевых узлов?

В моем курсе « Алгоритмы и структуры данных» профессора, слайды и книга ( Введение в алгоритмы, 3-е издание ) использовали слово NILдля обозначения, например, дочернего элемента узла (в дереве), который не существует. Однажды, во время лекции, вместо того, чтобы сказать NIL, мой одноклассник сказал...

15
Что означает ?

Что означает ?журналO ( 1 )NlogO(1)⁡n\log^{O(1)}n Я знаю нотацию big-O, но эта нотация для меня не имеет смысла. Я тоже ничего не могу найти по этому поводу, потому что поисковая система не может правильно это интерпретировать. Для некоторого контекста предложение, в котором я нашел это, гласит:...

15
Почему в основной теореме есть условие регулярности?

Я читал Введение в алгоритмы от Cormen et al. и я читаю формулировку основной теоремы, начиная со страницы 73 . В случае 3 также существует условие регулярности, которое необходимо выполнить, чтобы использовать теорему: ... 3. Если f(n)=Ω(nlogba+ε)е(N)знак равноΩ(Nжурналб⁡a+ε)\qquad \displaystyle...

14
n * log n и n / log n от времени полинома

Я понимаю, что быстрее, чем и медленнее, чем . Мне трудно понять, как на самом деле сравнить и с где .Θ ( n log n ) Θ ( n / log n ) Θ ( n log n ) Θ ( n / log n ) Θ ( n f ) 0 < f < 1Θ(n)Θ(n)\Theta(n)Θ(nlogn)Θ(nlog⁡n)\Theta(n\log n)Θ(n/logn)Θ(n/log⁡n)\Theta(n/\log n)Θ(nlogn)Θ(nlog⁡n)\Theta(n...

14
Нахождение максимального XOR двух чисел в интервале: можем ли мы сделать лучше, чем квадратичное?

Предположим, нам даны два числа и и мы хотим найти для .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Наивный алгоритм просто проверяет все возможные пары; например, в ruby ​​у нас будет: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if (i ^ j > max) max...

14
Что означает тильда в нотации big-O?

Я читаю статью, и в своем описании сложности времени говорится, что сложность времени равна .О~( 22 н)O~(22n)\tilde{O}(2^{2n}) Я искал в интернете и википедии, но я не могу найти, что означает эта тильда в нотации big-O / Landau. В самой газете я также не нашел никаких подсказок по этому поводу....

14
Что не так с суммами терминов Ландау?

Я написал ∑i=1n1i=∑i=1nO(1)=O(n)∑i=1n1i=∑i=1nO(1)=O(n)\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n) но мой друг говорит, что это неправильно. Из шпаргалки TCS я знаю, что сумма также называется HnHnH_n которая имеет логарифмический рост по nnn ....

12
Бесконечная цепочка больших

Во-первых, позвольте мне написать определение большого чтобы сделать вещи явными.OOO f(n)∈O(g(n))⟺∃c,n0>0f(n)∈O(g(n))⟺∃c,n0>0f(n)\in O(g(n))\iff \exists c, n_0\gt 0 такое, что0≤f(n)≤cg(n),∀n≥n00≤f(n)≤cg(n),∀n≥n00\le f(n)\le cg(n), \forall n\ge n_0 Допустим, у нас есть конечное число функций:...

11
Асимптотический анализ для двух переменных?

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

11
Предлагая уточнения типов

На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...