Квадратичное сито — что означает o (1)?
Я пытаюсь реализовать Quadratic Sieve, и я заметил, что мне нужно выбрать границу гладкости B, чтобы использовать этот алгоритм. В сети я обнаружил, что B также обозначает exp ((1/2 + o (1)) (log n log log n) ^ (1/2)), но теперь моя проблема — o (1). Не могли бы вы сказать мне, что означает o (1)?
Решение
Начнем с вашего ответа:
Определение f (n) как o (1) состоит в том, что limn → ∞f (n) = 0. Это означает, что для всех ϵ> 0 существует Nϵ, зависящее от ϵ, такое, что для всех n≥Nϵ | f (n) | ≤ϵ.
Или простым языком:
Обозначение o (1) означает «функцию, которая сходится к 0.»
Это фантастический ресурс: http://bigocheatsheet.com
Посмотрите на Обозначение асимптотического роста раздел
Ответ также можно найти в этом повторяющемся сообщении: Разница между обозначениями Big-O и Little-O
f ∈ O (g) говорит, по существу
За хотя бы один Выбрав постоянную k> 0, можно найти постоянную a такую, что неравенство f (x) < k g (x) выполняется для всех x> a.
Обратите внимание, что O (g) — это множество всех функций, для которых выполняется это условие.
f ∈ o (g) говорит, по существу
За каждый Выбрав постоянную k> 0, можно найти постоянную a такую, что неравенство f (x) < k g (x) выполняется для всех x> a.
Другие решения
O (1) означает, что требуется постоянное время, не зависящее от размера ввода.
o (1) (немного отличается!) означает, что функция, которую он представляет, сходится к 0.
Я бы не слишком беспокоился о граничности гладкости, сначала напишу остальную часть гораздо более сложного алгоритма, используя очень простую формулу гладкости. (первые 100 000 простых чисел или первые n простых чисел, где n = c * log (число)) Как только остальная часть алгоритма заработает (и, возможно, оптимизирована?), тогда тщательный выбор граничной гладкости действительно будет иметь значительный эффект. Эта длинная сложная формула, которую вы задали в этом вопросе, является приблизительным (асимптотическим) временем работы самого алгоритма квадратичного сита, я уверен, что он не связан с выбором границы гладкости.