Какова временная сложность следующей функции в нотации big-O?

Question

Я работаю над пониманием большого O и столкнулся с непростой проблемой.

Когда я смотрю на этот код, я сразу думаю о O (n), просто глядя на цикл for, но на строку

result = result * k

заставляет меня думать, что это что-то другое.

if power(int n, int k)
{
    int result = n
    for (int i = 1; i < n; i++){
        result = result * k
    }
}

Просто ищу четкое объяснение, почему я могу или не могу ошибаться

Answer 1

Это только утверждение, это не группа операторов, итерации которых не зависят от n.Итак, мы знаем об этом результате = result * k, это в O (1), в любом случае его временная сложность не может измениться.временная сложность вашего кода O (n) не более O (n)

Answer 2

Это не сложная проблема, если вы не используете язык, такой как C ++, который допускает перегрузку операторов, и метод operator * () типов k или result не перегружен, или же есть автономный (бесплатный).) перегруженный операторный метод, определенный с этими типами в качестве аргументов.Я предполагаю, что это не так, поэтому:

Ваш цикл имеет порядок O (n).Что вы делаете в этом цикле?Вы делаете еще один цикл?Или вызвать метод, который делает это?Нет. Сложность оператора вашей системы зависит от размера ее операндов?Возможно, технически да, поскольку 32-разрядное умножение будет быстрее на 32-разрядном ядре, чем 64-разрядное умножение, но оно основано на типах операндов, а не на значениях операндов.Операции умножения обычно имеют порядок O (1).

Таким образом, общая сложность составляет O (n * 1) или просто O (n).

Единственный способ - это что-то кромеO (n) - если оператор умножения перегружен и реализован наивным способом;например, если он делает целочисленное умножение, повторяя k раз и добавляя result к себе k раз. В этом случае общая сложность будет равна O (n ² ).

Но в любом нормальном случае сложность равна просто O (п).