Как мы можем предположить, что основные операции над числами занимают постоянное время?

74

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

Есть ли доказательства, показывающие, что сравнение двух чисел (или других примитивных арифметических функций) может быть выполнено в ? Если нет, то почему мы говорим, что сортировка на основе сравнения - это ? $O(1)$ $O(n\log n)$

Я столкнулся с этой проблемой , когда я ответил так вопрос , и я понял , что мой алгоритм не , потому что рано или поздно я должен иметь дело с большим-ИНТ, и это не алгоритм псевдо полиномиальное время он был . $O(n)$ $P$

algorithms complexity-theory algorithm-analysis time-complexity reference-question Рафаэль
источник

3

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

-битных чисел, размер входного бита равен

и сортировка может быть выполнена за

времени.

N

$N$

w

$w$

n = N w

$n=Nw$

O (N w \log N) = O (n \log n)

$O(Nw \log N) = O(n \log n)$

Сашо Николов

2

Есть в основном две "сферы" или "режимы" изучения сложности. обычно операции

предполагаются для операций «фиксированной ширины», что является разумным приближением для большинства компьютерных языков, которые имеют числовые представления фиксированной ширины, в том числе для чисел с плавающей запятой, например, 2-4 байта (см., например, стандарты IEEE). затем существует «арифметика произвольной точности», где числа имеют произвольный размер, и существует более тщательное / точное изучение сложности операций. первый контекст больше относится к прикладному анализу, а второй - к теоретическому / абстрактному анализу.

O (1)

$O(1)$

ВЗН

75

Для таких людей, как я, которые изучают алгоритмы для жизни, стандартная модель вычислений 21-го века - это целочисленная RAM . Модель предназначена для более точного отражения поведения реальных компьютеров, чем модель машины Тьюринга. Реальные компьютеры обрабатывают многоразрядные целые числа в постоянное время, используя параллельное оборудование; не произвольные целые числа, но (поскольку размеры слов неуклонно растут с течением времени), а также целые числа фиксированного размера .

Модель зависит от одного параметра , называемого размером слова . Каждый адрес памяти содержит одно битное целое число или слово . В этой модели входной размер - это количество слов на входе, а время выполнения алгоритма - это количество операций над словами . Стандартные арифметические операции (сложение, вычитание, умножение, целочисленное деление, остаток, сравнение) и логические операции (побитовое и, или, xor, сдвиг, вращение) над словами требуют времени по определению . $w$ $w$ $n$ $O(1)$

Формально размер слова НЕ является константой $w$ для анализа алгоритмов в этой модели. Чтобы привести модель в соответствие с интуицией, нам требуется , поскольку в противном случае мы даже не можем хранить целое число в одном слове. Тем не менее, для большинства нечисловых алгоритмов время выполнения фактически не зависит от , потому что эти алгоритмы не заботятся о базовом двоичном представлении их входных данных. И Mergesort, и Heapsort работают за ; медиана 3-х быстрой сортировки выполняется в $w \ge \log_2 n$ $n$ $w$ $O(n\log n)$ Время в худшем случае. Одним заметным исключением является двоичная радикальная сортировка, которая выполняется за время . $O(n^2)$ $O(nw)$

Установка дает нам традиционную модель оперативной логарифмической стоимости. Но некоторые алгоритмы целочисленного ОЗУ предназначены для больших размеров слов, например алгоритм целочисленной сортировки по линейному времени, разработанный Andersson et al. , что требует . $w = \Theta(\log n)$ $w = \Omega(\log^{2+\varepsilon} n)$

Для многих алгоритмов, возникающих на практике, размер слова просто не является проблемой, и мы можем (и делаем) прибегнуть к гораздо более простой модели ОЗУ с одинаковой стоимостью. Единственная серьезная трудность связана с вложенным умножением, которое можно использовать для очень быстрого построения очень больших целых чисел . Если бы мы могли выполнять арифметику с произвольными целыми числами за постоянное время, мы могли бы решить любую проблему в PSPACE за полиномиальное время . $w$

Обновление: я должен также упомянуть, что есть исключения из «стандартной модели», такие как алгоритм целочисленного умножения Фюрера , который использует многолинейные машины Тьюринга (или, что эквивалентно, «битовая память»), и большинство геометрических алгоритмов, которые анализируются теоретически чистая, но идеализированная модель "реального ОЗУ" .

Да, это банка червей.

JeffE
источник

3

Я знаю, что просто должен проголосовать, но не могу удержаться от того, чтобы сказать это: это лучший ответ. Хитрость в том, что (1) арифметические операции имеют постоянное время по определению, и это нормально, потому что теоретически вы можете выбрать любую модель, и (2) у вас должны быть некоторые причины для выбора определенной модели, и этот ответ объясняет, что это такое.

rgrig

n

$n$

m

$m$

P

$P$

1

w

$w$

w

$w$

N

$N$

0

$0$

M

$M$

N \log_{w} M = (N \lg M) / (\lg w)

$N\log_w M = (N\lg M)/(\lg w)$

O (N M)

$O(NM)$

M

$M$

Джефф

Есть ли какие-либо алгоритмы, проанализированные в модели Real RAM, которые не являются тайными алгоритмами "Order Type RAM"? Я никогда не думал об этом много, но не могу быстро придумать пример, который не так.

Луи

1

O (n^{3})

$O(n^3)$

O (n^{4})

$O(n^4)$

24

$n$ $O(1)$ $O(n)$

Массимо Кафаро
источник

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

1

n

$n$

θ (n^{1 / 2})

$\theta(n^{1/2})$

P

$P$

n

$n$

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

Массимо Кафаро

P

$P$

P

$P$

O (n \log n)

$O(n \log n)$

n

$n$

O (1)

$O(1)$

n

$n$

O (n) = O (2^{l g n})

$O(n) = O(2^{lg n})$

l g n

$lg n$ размер ввода, алгоритм экспоненциальный в размере ввода! Думать об этом. Теперь вы можете понять, что я имею в виду под «Все зависит от контекста».

Массимо Кафаро

16

Чтобы ответить на поставленный вопрос: алгоритмисты просто делают это довольно часто, используя модель ОЗУ. Для сортировки во многих случаях люди даже анализируют более простую модель сравнения , о которой я немного подробнее расскажу в связанном ответе.

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

Чтобы ответить на неявное продолжение о численных алгоритмах: Нет, старая модель ОЗУ здесь не стандартная. Даже устранение Гаусса может потребовать некоторой осторожности. Как правило, для вычисления ранга вводится лемма Шварца (например, раздел 5 здесь ). Другим каноническим примером является анализ алгоритма эллипсоида, который требует некоторой осторожности для анализа.

И наконец: люди думали о сортировке строк раньше , даже недавно.

Обновление: проблема с этим вопросом заключается в том, что «мы» и «предположим» не так точно определены. Я бы сказал, что люди, которые работают в модели RAM, не занимаются численными алгоритмами или теорией сложности (где определение сложности деления было знаменитым результатом ).

Луис
источник

Хм, кажется, это интересный ответ ....

Есть ли причина, по которой он не полностью отвечает на вопрос?

Луи

7

$O(1)$ $O(1)$

python -mtimeit "$a * $b"$a $10^{\{1,2,...,66\}}$ $b = 2*$a

$10^{50}$ $\log_{10}(\tt{sys.maxint})$

Дугал
источник

O (n)

$O(n)$

O (n \cdot \log n \cdot \log m)

$O(n \cdot \log n \cdot \log m)$

7

$O(1)$

$O(\log M)$ $O (N \log N)$ $O (N \log N \log M)$

$M$

Эрель Сегал-Халеви
источник

O (\log m)

$O(\log m)$

O (\log n)

$O(\log n)$

m

$m$

O (l o g N)

$O(log N)$

n

$n$

n^{n^{n}}

$n^{n^n}$

Вы правы, я исправил свой ответ.

Эрель Сегал-Халеви

4

Я бы сказал, что мы обычно принимаем O (1) арифметические операции, потому что мы обычно делаем вещи в контексте 32-битных целых или 64-битных целых чисел или чисел с плавающей запятой IEEE 754. O (1), вероятно, является довольно хорошим приближением для такого рода арифметики.

Но в целом это не так. В общем, вам нужен алгоритм для выполнения сложения, вычитания, умножения и деления. Вычислительность и логика Булоса, Берджесса и Джеффериса приходят на ум как способ понять доказательство (я) этого, с точки зрения пары различных формальных систем, рекурсивных функций и машин Abacus, по крайней мере, в моей копии 4-го издания.

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

Брюс Эдигер
источник

Как мы можем предположить, что основные операции над числами занимают постоянное время?

Ответы: