Почему предполагается, что временная сложность умножения на n постоянна?

Question

Независимо от того, как реализована операция умножения (или деления) (т. Е. Программная функция или аппаратная инструкция), она не будет разрешима во времени O(1). для больших n значений процессор не может даже вычислить его по одной инструкции.

В таких алгоритмах почему эти операции постоянны и не зависят от n?

for (i = 1; i <= n; i++) {
    j = n;
    while (j > 1)
        j = j / 3;    //constant operation
}

Answer 1

Сложность времени не является мерой времени. Это мера «базовых операций», которую можно определить так, как вы хотите. Часто любая арифметическая операция считается базовой операцией. Иногда (например, при рассмотрении временной сложности алгоритмов сортировки или операций с хэш-таблицами) основными операциями являются сравнения. Иногда «базовыми операциями» являются операции над одиночными битами (в этом случае j=j/3 будет иметь временную сложность O (log (j)).

Правила, которым нужно следовать:

• если вы говорите о сортировке или хеш-таблицах, базовые операции - это сравнения
• если вы говорите о каком-либо другом практическом алгоритме, то основными операциями являются арифметические операции и присваивания.
• если вы говорите о классах P / NP, базовые операции - это количество шагов детерминированной машины Тьюринга. (Я думаю это эквивалентно битовым операциям).
• если вы говорите о практических алгоритмах в качестве эксперта по теории сложности, вы часто будете предполагать, что базовые типы имеют ~ log n битов, а базовые операции - это арифметические операции и присваивания этих ~ log n битовых слов.