Независимо от того, как реализована операция умножения (или деления) (т.е. является ли это программной функцией или аппаратной инструкцией), она не будет решена во времени O(1)
. при больших значениях n
процессор не может даже вычислить его по одной инструкции.
Почему в таких алгоритмах эти операции постоянны и не зависят от n
?
for (i = 1; i <= n; i++) {
j = n;
while (j > 1)
j = j / 3; //constant operation
}
Обычно умножение собственных типов составляет O (1) (постоянное время). Типы больших целых чисел, такие как используемые в Java, .NET и других средах, обычно имеют более высокую сложность. См., Например, javaspecialists.eu/archive/Issue236.html.
@JimMischel, мы вычисляем сложность для больших n значений. поэтому мы должны позволить n быть как можно большим. тогда почему умножение на n постоянное? (насколько я знаю, обычно считается постоянным)
Просто примите это как предположение (иногда принимаемое), показывающее разрыв между теорией и практикой. С теоретической точки зрения вы также можете подвергнуть сомнению постоянную сложность сложения, учитывая физику: скорость света и верхний предел плотности информации на площадь / объем (до того, как все потеряно в черной дыре).
Пожалуйста, перечитайте мой комментарий. Если ваш n
является собственным типом (например, long
или double
), то значение не имеет значения. Система может умножать на 9324568078 так же быстро, как и на 7. Если n
какой-то другой, неродной тип (например, BigInteger
), то умножение имеет более высокую сложность, как описано в статье, на которую я ссылался.
Умножение произвольной точности за один шаг машины - это физически нереалистичная лазейка, которая добавляет удивительное количество мощности машине, которая, как предполагается, имеет это - см. cs.stackexchange.com/questions/76797/…. Мелкий шрифт большинства теоретических машин запрещает это, обычно говоря, что нельзя предполагать, что числа становятся слишком большими, или не обеспечивает умножение, которого достаточно, чтобы числа оставались в разумном диапазоне.
Сложность времени - это не мера времени. Это мера «основных операций», которую можно определить по своему усмотрению. Часто любая арифметическая операция считается базовой. Иногда (например, при рассмотрении временной сложности алгоритмов сортировки или операций с хеш-таблицами) основными операциями являются сравнения. Иногда «базовые операции» - это операции с отдельными битами (в этом случае j=j/3
будет иметь временную сложность O (log (j)).
Как правило, соблюдаются следующие правила:
Как это будет реализовано, зависит от базовой архитектуры. В большинстве практических случаев это не имеет значения и может быть ограничено достаточно большой константой. Фактически, константа может быть максимально возможным значением, и в этом случае операция немедленно ограничивается. В любом случае, это обычно не имеет отношения к анализируемому алгоритму и только искажает то, что нас действительно интересует.