Википедия перечисляет временную сложность сложения как , где - количество битов.н
Это жесткая теоретическая нижняя граница? Или это просто сложность самого быстрого известного алгоритма. Я хочу знать, потому что сложность сложения подчеркивает все другие арифметические операции и все алгоритмы, которые их используют.
Теоретически невозможно получить алгоритм сложения, который работает в ? Или мы связаны с линейной сложностью для сложения.
источник
Чтобы анализ сложности вообще имел какой-либо формальный смысл, вы должны указать формальную вычислительную модель, в которой выполняется алгоритм в объекте, или, по крайней мере, модель затрат , которая определяет основные операции и их расходы.
В большинстве случаев предполагается, что арифметические операции занимают времени. Обычно это разумно, так как нас интересует алгоритмическая сложность независимо от участвующих чисел. Это называется моделью равномерной стоимости .Θ ( 1 )
Если числа могут расти неограниченно, или мы заинтересованы в анализе самих операций, считаются, что арифметические операции имеют стоимость , пропорциональную размеру ввода.Θ ( | x | )
Теперь, операции могут иметь стоимость, которая меньше, чем это? Возможно, однако, вам придется формально определить вычислительную модель, в которой это может произойти.
источник
Представьте , что ваш алгоритм успешно добавляет 1010100110 и 0010010110 без чтения каждого бита. Для того , алгоритм , чтобы иметь возможность добавлять произвольные входы, я должен быть в состоянии случайно перевернуть любой из этих битов, и выходной алгоритм еще правильный (но разные) сложение. Но если ваш алгоритм не читает каждый бит, как он может сказать, что перевернутый ввод отличается от исходного ввода?
источник