Временная сложность сложения

11

Википедия перечисляет временную сложность сложения как , где - количество битов.нNN

Это жесткая теоретическая нижняя граница? Или это просто сложность самого быстрого известного алгоритма. Я хочу знать, потому что сложность сложения подчеркивает все другие арифметические операции и все алгоритмы, которые их используют.

Теоретически невозможно получить алгоритм сложения, который работает в ? Или мы связаны с линейной сложностью для сложения.o(n)

Тоби Алафин
источник

Ответы:

17

Если ваш алгоритм использует асимптотически меньше времени, то у него недостаточно времени для чтения всех цифр добавляемых чисел. Вы должны представить, что обрабатываете очень большие числа (хранятся, например, в текстовых файлах 8 МБ). Конечно, сложение может быть сделано очень быстро по сравнению со значением чисел; он выполняется за время O ( log ( N ) ) , если N является значением суммы.NО(журнал(N))N

Это не значит, что вы можете немного ускорить процесс; если ваш процессор обрабатывает 32 бит каждой операции, то вы используете раза, но это все ещеO(n),а неo(n).N32О(N)о(N)

Лиуве Винхуйзен
источник
Читает все данные теоретически необходимо. Для сложения любых двух чисел и b , a : a b , a + b 2 a . Вычисление 2 a , может быть сделано в операции O ( 1 ) , через сдвиг. Добавление 0 . Считают, что. Если вы не можете найти более быструю оценку суммы, уточните ее, пока она не станет правильной. Менее чем за n операций? aб,a:aб,a+б2a2aО(1)0N
Тоби Алафин
3
Да, это теоретическая необходимость, потому что: каждый бит ввода используется нетривиально в выводе , где под нетривиальным я подразумеваю, что это не единичная функция. В вашем примере, является ли 2 может быть вычислена в O ( 1 ) зависит от времени на расчетной модели: если присоединени 0 является операцией постоянная времени, то да. Если у вас есть доступ к ОЗУ, вам нужно O ( log ( n ) ), чтобы записать адрес бита, если вы уже знаете длину a или O ( n )2a2aО(1)0О(журнал(N))aО(N)время , если вы должны прочитать все выяснить. В этом 2 в примере, многие выходные биты являются тривиальными функциями входных бит. a2a
Lieuwe Vinkhuijzen
У меня есть алгоритм , который находит длину в O ( журнал N ) . Он использует бинарный поиск. aО(журналN)
Тоби Алафин
3
@TobiAlafin Если ваша модель поддерживает адресацию ОЗУ, тогда ваш двоичный поиск выполняется за шагов, правильно. На Turing Machine и в текстовом файле, не загруженном в основную память, это занимает O ( n ) времени. В любом случае, чтобы ответить на ваш вопрос, с или без адресации ОЗУ для ускорения поиска, ваш алгоритм должен будет просмотреть все биты ввода, чтобы вычислить a + b . Предположим, что это не так, и на входе в 42 бита он не проверяет 6-й бит. Тогда я мог бы перевернуть этот бит, и это дало бы неправильный ответ. О(журналN)О(N)a+б426
Lieuwe Vinkhuijzen
1
Ω(N)
7

Чтобы анализ сложности вообще имел какой-либо формальный смысл, вы должны указать формальную вычислительную модель, в которой выполняется алгоритм в объекте, или, по крайней мере, модель затрат , которая определяет основные операции и их расходы.

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

Если числа могут расти неограниченно, или мы заинтересованы в анализе самих операций, считаются, что арифметические операции имеют стоимость , пропорциональную размеру ввода.Θ(|Икс|)

Теперь, операции могут иметь стоимость, которая меньше, чем это? Возможно, однако, вам придется формально определить вычислительную модель, в которой это может произойти.

быстрая сортировка
источник
1
Θ(logn)N
3

Ω(N)

Представьте , что ваш алгоритм успешно добавляет 1010100110 и 0010010110 без чтения каждого бита. Для того , алгоритм , чтобы иметь возможность добавлять произвольные входы, я должен быть в состоянии случайно перевернуть любой из этих битов, и выходной алгоритм еще правильный (но разные) сложение. Но если ваш алгоритм не читает каждый бит, как он может сказать, что перевернутый ввод отличается от исходного ввода?

murrdpirate
источник
N
Абсолютно. Вы просто должны определить , что такое «приближенными» означает в вашем алгоритме. В зависимости от этого определения, добавив два наиболее значимых битов может быть приблизительная сумма, которая может быть сделано в O (N) времени. Когда вы упоминаете алгоритм «сложения», я думаю, мы все понимаем, что ответ должен быть точным.
murrdpirate