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

Question

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

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

---

Я столкнулся с этой проблемой, когда ответил на вопрос, и я понял, что мой алгоритм не является $ o (n) $, потому что рано или поздно я должен иметь дело с биржом, также это был не псевдономиальный алгоритм времени, это был $ p $.

Answer 1

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

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

Формально, Размер слова $ w $ не является постоянным Для целей анализа алгоритмов в этой модели. Чтобы сделать модель в соответствии с интуицией, нам требуется $ w ge log_2 n $, поскольку в противном случае мы даже не можем хранить целое число $ n $ в одном словом. Тем не менее, для большинства немерных алгоритмов время работы на самом деле не зависит от $ W $, потому что эти алгоритмы не заботятся о базовом бинарном представлении их вклада. Mergesort и Heapsort оба работают в $ O (n log n) $ времени; Медиана 3-й циккорт работает в $ O (n^2) $ времени в худшем случае. Одним из заметных исключений является бинарная Radix Sort, которая работает в $ O (NW) $ Time.

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

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

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

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

Answer 2

Это только зависит от контекста. При работе с Сложность бита Из алгоритмов мы не говорим, что добавление двух номеров $ n $ bits равно $ O (1) $, мы говорим, что это $ O (n) $. Точно так же для умножение и т.п.

Answer 3

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

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

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

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

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

Answer 4

Я не смог найти никаких исследований этого, но Козен говорит во введении в «дизайн и анализ алгоритмов», которые модель $ O (1) $ более точно отражает экспериментальное наблюдение [чем модель log-cost] для данных умеренного размера (поскольку умножение действительно занимает одну единицу времени) ». Он также дает ссылку на Эта бумага В качестве примера того, как модель $ O (1) $ может быть использована.

Это абсолютно не законная оценка (не в последнюю очередь потому, что это Python), но вот некоторые цифры из бега python -mtimeit "$a * $b" за $a в $ 10^{ {1,2, ..., 66 }} $ и $b = 2*$a. Анкет (Я остановился в 66, потому что именно тогда синтаксис Python перестает принимать целочисленные литералы, и мне придется слегка переключить код оценки, так что я этого не сделал .: P)

Каждое число составляет среднее значение 10 000 000 петлей, где он занимает лучшее время в 3 пробега в каждой петле. Я бы сделал стержни ошибок или что -то в этом роде, но это было бы больше усилий. : P В любом случае, это выглядит довольно постоянно для меня, даже до $ 10^{50} $ - немного удивительно, так как $ log_ {10} ( tt {sys.maxint}) $ 43, что усиливает мой подозрение, что, возможно, эта оценка особенно подделана, и я должен сделать это в C.

Answer 5

Вы правы, в целом мы не можем предположить, что они $ O (1) $.

Строго говоря, если мы хотим сортировать массив с помощью n чисел с использованием сравнений, а наибольшее число - m, то в худшем случае каждое сравнение может включать сравнения $ o ( log m) $ на уровне битов. И если наш алгоритм выполняет сравнения $ O (n log n) $, то его общая сложность будет $ O (n log n log m) $.

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

Answer 6

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

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

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